Discrete Mathematical Structures by Pearson

Topics in Graph Theory 10-25

10.9 REPRESENTATION OF MULTI GRAPH

When graph G is a multigraph, then a

ij

is the number of edges joining the vertex v

i

to the vertex v

j

.

Let G be a multigraph consisting of n vertices, then the n × n adjacency matrix A = [a

ij

] is

defined by,

a

ij

= k

= 0

where k is the number of edges joining the vertex v

i

to the vertex v

j

otherwise.

The adjacency matrix of order 4 × 4 for the multigraph shown in Fig. 10.31 is the following:

vv

vv

A

v

v

v

v

1

234

1

2

3

4

01

32

1110

310

2

001

=

























0

v

4

v

3

v

2

v

1

Figure 10.31

Example 1  Find the adjacency matrix and the incident matrix of the multigraph shown in Fig. 10.32

vv

vv

A

v

v

v

v

1

234

1

2

3

4

01

21

1010

2

101

1011 ...