Adjacency matrices

Suppose that is a simple graph where . Suppose that the vertices of G are listed arbitrarily as . The adjacency matrix A (or A_G) of G, with respect to this listing of the vertices, is the zero-one matrix with 1 as its (i, j)^th entry when v_i and v_j are adjacent, and 0 as its (i, j)^th entry when they are not adjacent. In other words, if its adjacency matrix is , then .

Example. Use an adjacency matrix to represent the graph shown in Figure below.

Solution: We order the vertices as a, b, c, d. The matrix representing this graph is .

Example. Draw a graph with the adjacency matrix with respect to the ordering of vertices a, b, c, d.

Solution:

Adjacency matrices can also be used to represent undirected graphs with loops and with multiple edges. A loop at the vertex a_i is represented by a 1 at the (i, i)^th position of the adjacency matrix. When multiple edges are present, the adjacency matrix is no longer a zero-one matrix, since the (i, j)^th entry of this matrix equals the number of edges that are associated to .

Example. Use an adjacency matrix to represent the pseudograph shown in Figure below.

Solution: The adjacency matrix using the ordering of vertices a, b, c, d is .

Дата добавления: 2014-12-23