3.2 Matrix Representation of Graphs
Although a pictorial representation of a graph is very convenient for a visual study, other representations are better for computer processing. A matrix is a convenient and useful way of representing a graph to a computer. Matrices lend themselves easily to mechanical manipulations. Besides, many known results of matrix algebra can be readily applied to study the structural properties of graphs from an algebraic point of view. In many applications of graph theory, such as in electrical network analysis and operation research, matrices also turn out to be the natural way of expressing the problem.
3.2.1 Incidence Matrix
Let G be a graph with n vertices, e edges, and no self-loops. Define an n by e matrix A =[aij], whose n rows correspond to the n vertices and the e columns correspond to the e edges, as follows:
The matrix element
Aij = 1, if jth edge ej is incident on ith vertex vi, and
= 0, otherwise.
(a)
a b c d e f g h
v1 0 0 0 1 0 1 0 0
v2 0 0 0 0 1 1 1 1
v3 0 0 0 0 0 0 0 1
v4 1 1 1 0 1 0 0 0
v5 0 0 1 1 0 0 1 0
v6 1 1 0 0 0 0 0 0
(b)
Fig. 3-4 Graph and its incidence matrix.
Such a matrix A is called the vertex-edge incidence matrix, or simply incidence matrix. Matrix A for a graph G is sometimes also written as A(G). A graph and its incidence matrix are shown in Fig. 3-4. The incidence matrix contains only two elements, 0 and 1. Such a matrix is called a binary matrix or a (0, 1)-matrix.
The following observations about the incidence matrix A can readily be made:
Since every edge is incident on exactly two vertices, each column of A has exactly two 1�s.
The number of 1�s in each row equals the degree of the corresponding vertex.
A row with all 0�s, therefore, represents an isolated vertex.
Parallel edges in a graph produce identical columns in its incidence matrix, for example, columns 1 and 2 in Fig. 3-4.
