Let G be a graph with vertices v1, v2,…, vm and edges e1, e2, …,en. It is sometimes practical, especially for computational reasons, to represent G by a matrix. Note that the edges of G can be represented by an n×2 integer matrix B where each row of B denotes edge of G, e.g. the row (3 ,4) would denote the edge (v3, v4). This edge matrix B does not completely describe. G unless we are also given the number m of vertices of G.. We discuss two other widely used matrix representations of G.
(1) Adjacency matrix. Let A = (aij) be the m×m matrix defined by
Then A is called the adjacency matrix of G.. Observe that aij =aji; hence A is a symmetric matrix.(We define an adjacency matrix for a multigraph by letting aij denote the number of edges{ vi, vj}.)
(2) Incident matrix. Let M = (mij) be the m×n matrix defined by
Consider, for example, the graph in Fig.5-12. Its edge matrix B, adjacency matrix A, and incidence matrix M follow. For easy reading, we have labeled the rows and columns of A and M by the corresponding vertices and edges.
Although the edge matrix B of a graph G is the most compact representation, it is not always the most useful. In view of the following theorem, the adjacency matrix is very useful in deciding questions of connectivity.
Theorem: Let A be the adjacency matrix of a graph G with m vertices where m>1.Then the ij entry of the matrix An gives the number of walks of length n from the vertex vi to the vertex vj.
(An analogous theorem, for directed graphs (Theorem 7.8) is stated and proved in Chapter 7.)
Since G has m vertices, any path from vi to vj, must have length m-1 or less. Hence the matrix A+A2+... +Am-1 can have a zero ij entry only if there is no path from vi to vj.
By the connection matrix of a graph G with m vertices, we mean the m×m matrix C = (cij). where
Note that G is connected if and only if C has no zero entry. The above discussion shows that C and the matrix A+A2+... +Am-1 have the same zero entries off the main diagonal.
|
