One Stop GATE Forum: Matrix Representation of graph

Message

   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 =[a_ij], whose n rows correspond to the n vertices and the e columns correspond to the e edges, as follows:
The matrix element
	A_ij = 1, 	if  j^thedge e_j is incident on i^th vertex v_i, 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.

Author	Message
sumana Newbie Joined: 08Apr2007 Online Status: Offline Posts: 9	Topic: Matrix Representation of graph Posted: 08Apr2007 at 10:18pm
	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 =[a_ij], whose n rows correspond to the n vertices and the e columns correspond to the e edges, as follows: The matrix element A_ij = 1, if j^thedge e_j is incident on i^th vertex v_i, 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. Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers