[PDF] 1.10 Matrix Representation of Graphs - Definitions

View - Download 1.10 Matrix Representation of Graphs - Definitions

Previous PDF

Next PDF

42Basic Concepts of Graphs

1.10 Matrix Representation of Graphs

Definitions:

In this section, we introduce two kinds ofmatrix representationsof a graph, that is, the adjacency matrix and incidence matrix of the graph. A graphGwith the vertex-setV(G) ={x1,x2,···,vv}can be described by means of matrices. Theadjacency matrixofGis av×vmatrix

A(G) = (aij),whereaij=μ(xi,xj) =|EG(xi,xj)|.

For example, for the digraphDand the undirected graphGshown in Figure 1.26, their adjacency matricesA(D) andA(G) are as follows.

A(D) =((((0 2 0 00 0 0 01 1 0 11 0 0 1))))

,A(G) =((((0 2 1 12 0 1 01 1 0 11 0 1 1)))) .x1x2 x3x4 a1 a2 a3 a4 a5a6a7D: x1x2 x3x4 e1 e2 e3 e4 e5e6e7G:

Figure 1.26:A digraphDand an undirected graphG

The incidence matrixof a loopless graphGis av×εmatrix

M(G) = (mx(e)), x?V(G) ande?E(G),

where, ifGis directed, then m x(e) =???1,ifxis the tail ofe; -1,ifxis the head ofe;

0,otherwise,

and ifGis undirected, then m x(e) =?1,ifeis incident withx;

0,otherwise.

For example, for the digraphDand the undirected graphGshown in Figure 1.26, the incidence matrixM(D-a7) andM(G) are as follows.

M(D-a7) =((((1 1 0 0-1-1

-1-1-1 0 0 0

0 0 1 1 0 1

0 0 0-1 1 0))))

1.10. MATRIX REPRESENTATION OF GRAPHS43

M(G) =((((1 1 0 0 1 1 01 1 1 0 0 0 00 0 1 1 0 1 00 0 0 1 1 0 2)))) The adjacency matrix or the incidence matrix of a graph is another representation of the graph, and it is this form that a graph can be commonly stored in computers. The matrix representation of a graph is often convenient if one intends to use a computer to obtain some information or solve a problem concerning the graph. This kind of representation of a graph is conducive to study properties of the graph by means of algebraic methods. Let

σ=?1 2···n

i

1i2···in?

be a permutation of the set{1,2,···,n}. Then we obtain ann×n permutation matrix

P= (pij) defined by

p ij=?1,ifj=σ(i);

0,otherwise.

It is not difficult to see that the adjacency matrices of two isomorphic graphs are permutedly similar. In other words, assume thatAandBare the adjacency matrices of two isomorphic graphsGandH, respectively, then there exists av×v permutation matrixPsuch thatA=P-1BP. Similarly, the incidence matrices of two isomorphic graphsare permutedly equiv- alent. In other words, assume thatMandNare the incidence matrices of two iso- morphic graphsGandH, respectively, then there exist av×vpermutation matrix Pand anε×εpermutation matrixQsuch thatM=PNQ. Relationship between Matrix and Graphical Representa- tions: It is these properties that makes us convenient to study structures of graphs by using their matrix representations. We now present a veryuseful result on the adjacency matrix of a graph as follows. Theorem 1.11 Let A be the adjacency matrix of a digraph Gwith the vertex set{x1,x2,···,xv}. Then the entry in position (i,j)of Akis the number of different(xi,xj)-walks of lengthk inG. Proof:The proof is by induction onk. The result is obvious fork= 1 since there existaij(xi,xj)-walks of length one if and only if there existaijedges from

44Basic Concepts of Graphs

x itoxjinG. LetAk-1=? a(k-1) ij? and assume thata(k-1) ijis the number of different (xi,xj)-walks of lengthk-1 inG; furthermore, letAk=? a(k) ij? . Since A k=Ak-1·A, we have a (k) ij=v? l=1a(k-1) il·alj.(1.11) Every (xi,xj)-walk of lengthkinGconsists of an (xi,xl)-walk of lengthk-1, where x induction hypothesis and the equation (1.20), we have the desired result. It should be noted that walks could not be replaced by paths inTheorem 1.11 in general. It is easy to see that there is the unique (x,y)-walk of lengthnfor any pair (x,y) of vertices inB(d,n). We obtain from Theorem 1.11 immediately that ifA is the adjacency matrix ofB(d,n), thenAn=J, whereJis ann-square matrix all of whose entries are 1. Similarly, ifAis the adjacency matrix ofK(d,n), then A n+An-1=J.

Some Examples:

We will, in Section 1.11 this book, introduce an important application of the adjacency matrix of a graph, specially Theorem 1.11, in matrix theory. We here give three examples, which are important results in graph theory, to show that adjacency and incidence matrices are very useful for studying graphs. In Example 1.6.3, we show that ifGis a strongly connected digraph of orderv and the maximum degree Δ, then k+1-1

Δ-1,for Δ>1.

Digraphs attaining this upper bound are called

(Δ,k)-Moore digraphs. The following example is due to Plesnik and Znom (1974), and rediscovered by

Bridges and Toueg (1980).

Example 1.10.1 There is no(Δ,k)-Moore digraph forΔ≥2 andk≥2. Proof:Assume thatGis a (Δ,k)-Moore digraph whose ordernreaches the Moore bound defined in (1.6), and letAbe the adjacency matrix ofG. By the exercise 1.6.2,Gis a Δ-regular and simple digraph. Furthermore, by Theorem 1.11,

1.10. MATRIX REPRESENTATION OF GRAPHS45

we have

I+A+A2+···+Ak=J,(1.12)

whereIis an identity square matrix. The expression (1.12) impliesthatJis a polynomial inA, and so the matricesAandJhave a common set of eigenvectors. It is not difficult to show that Δ is an eigenvalue ofA(see the exercise 1.10.6). Letrbe any eigenvalue other than Δ, and letXbe an eigenvector corresponding to r. Noting that the zero, as an eigenvalue ofJ, has the multiplicityn-1, we have

AX=rX,JX= 0.

By (1.12), we obtain the relation

1 +r+r2+···+rk= 0.(1.13)

The expression (1.13) shows thatrhas the multiplicity (k+1) as the unite root, i.e., r k+1= 1. Letr1,r2,···,rn-1ben-1 eigenvalues ofAother than Δ. By Theorem

TrAi= 0, i= 1,2,···,k.

Thus the sum of the eigenvalues ofAi

i+n-1? j=1r ij= 0, i= 1,2···,k.(1.14)

Sincerj

rj=|rj|2= 1 =rk+1 j, it follows thatr-1 j=rj=rkj, whererjis the conjugate complex number ofrj. Settingi= 1 andi=kin (1.23), respectively, we have -Δ =n-1? j=1r j,-Δk=n-1? j=1r kj. Taking the conjugates of the above expressions and noting (1.14), we have that -Δ =n-1? j=1r -1j=n-1? j=1r kj=-Δk, which holds if and only if eitherk= 1 or Δ = 1. This contradicts to our assumption and, thus, the conclusion follows. By Example 1.10.1, a digraph with the maximum degree Δ and diameter 2 has order at most Δ

2+ Δ. We have known that the Kautz digraphK(Δ,2) had order

2+Δ. Therefore,K(Δ,2) is a maximum (Δ,2)-digraph, which is the unique known

maximum (Δ,2)-digraph up to now.

46Basic Concepts of Graphs

Similarly, ifGis a connected graph of ordervand the maximum degree Δ, then =???2k+ 1,for Δ = 2;

Δ(Δ-1)k-2

Δ-2,for Δ>2.

Graphs attaining this upper bound are called

(Δ,k)-Moore graphs. Example 1.10.2 (Hoffman and Singleton, 1960) There is no undirected(Δ,2)-Moore graph forΔ?= 2,3,7,57. ProofAssume thatGis an undirected (Δ,2)-Moore graph of ordern. ThenG is Δ-regular. The adjacency matrixA=A(G) is a real symmetricn-square matrix with all main diagonal entries 0. SinceGis Δ-regular, Δ is an eigenvalue ofA. Let Ibe the identityn-square matrix, andJbe ann-square matrix all of whose entries are 1. Thennis an eigenvalue ofJ, otherwise are 0. Noted(G) = 2. By Theorem

1.11, all main diagonal entries ofA2are Δ, otherwise are 0 or 1, and the (i,j)-th

entry ofA2is 0 if and only if the corresponding two vertices are adjacent inG, that is the (i,j)-th entry ofAis 1. It follows that A

2+A-(Δ-1)I=J.(1.15)

This implies thatJis a polynomial inA. SoAandJhave a common set of eigenvectors. Suppose that one of these isXcorresponding to the eigenvalue Δ. Then

AX= ΔX, JX=nX.

For this eigenvector, the expression (1.15) supplies the relation Δ2+ 1 =n. LetYbe any other eigenvector ofAcorresponding to an eigenvaluer. Then

AY=rY, JY= 0.

Using (1.15), we obtain the relation

r

2+r-(Δ-1) = 0.

HenceAhas two other distinct eigenvalues:

r 1=1

2(-1 +⎷4Δ-3 ), r2=12(-1-⎷4Δ-3 ).

SinceAis a real symmetric matrix, it has only real eigenvalues. Thus bothr1and r

2are real numbers.

1.10. MATRIX REPRESENTATION OF GRAPHS47

If Δ is such thatr1andr2are not rational, then each has multiplicity1

2(n-1)

as an eigenvalue ofAsinceAis rational. Since all main diagonal entries ofAare 0, by a result on the trace of a matrix, the sum of the eigenvaluesofAis 0. Namely 1

2(n-1)(r1+r2) = Δ-12Δ2= 0.(1.16)

The value of Δ satisfying (1.16) is only Δ = 2, for whichn= 5 and the corresponding undirected (2,2)-Moore graph is an undirected cycleC5. The values of Δ for whichr1andr2are rational are those for which there is an integerssuch thats2= 4Δ-3. Thus r 1=1

2(s-1), r2=-12(s+ 1).

Lettbe the multiplicity ofr1. Then the sum of the eigenvalues ofAis

Δ +ts-1

2+ (n-1-t)-s-12= 0.

Using the relationsn= 1 + Δ2ands2= 4Δ-3, we have that s

5+s4+ 6s3-2s2+ (9-32t)s= 15.(1.17)

Since the equation (1.17) requires solutions in integers, the only candidates forsare the factors of 15. These possible solutions are: s=±1, t= 0,Δ = 1, n= 2; s=±3, t= 5,Δ = 3, n= 10; s=±5, t= 28,Δ = 7, n= 50; s=±15, t= 1729,Δ = 57, n= 3250. There is no undirected graph of degree 1 and diameter 2. The theorem follows. The undirected (7,2)-Moore bound ism(7,2) = 50, the corresponding undi- rected (7,2)-Moore graph is determined by Hoffman-Singleton. The uniqueness of the undirected (3,2)- and (7,2)-Moore graphs have been shown by Hoffman and

Singleton.

The undirected (57,2)-Moorehas order 3250, the correspondingundirected (57,2)- Moore graph might exist, but no one has been able to construct(or prove the nonex- istence of) such a graph so far. Example 1.10.3 Let M be the incidence matrix of a digraph Gwithout loops, and let Mibe the matrix obtained from M by deleting theith row. Then the algebraic cofactor of any entry in MM

Tis equal to the determinant det(MiMTi), where

M

Tdenotes the transpose of M.

48Basic Concepts of Graphs

Proof:Suppose that the vertex-set ofGis{x1,x2,···,xv}, and letN=MMT. Suppose that the entry in position (i,j) ofNisnij. ThenNis symmetric and n ij=?dG(xi) =d+G(xi) +d-G(xi),forj=i; -μ(xi,xj)-μ(xj,xi),forj?=i. Thus the sum of any row and the sum of any column ofNall are 0. It is a routine algebraic exercise to show that the algebraic cofactors of all entries inMMThave the same value (the exercise 1.10.5). LetNijbe the algebraic cofactors ofnijin MM

T, and, without loss of generality, suppose

N

Letα1be the first row vector ofM. Then

N=MMT=?α1

M 1?

αT1MT1?

1αT1α1MT1

M

1αT1M1MT1?

Thus, we have

N as desired. We conclude this section with some remarks. LetAbe the adjacency matrix of an undirected graphGwith the vertex-set{x1,x2,···,xv},Mthe incidence matrix of any oriented graphDofG, and letBbe thev×vdiagonal matrix with the main diagonal entriesbii=dG(xi). It is easily shown that (the exercise 1.10.5) MM

T=B-A, which is called

Laplace matrixin the literature and textbook on

graph theory. We have known from Example 1.10.3 that all the algebraic cofactors of entries inMMThave the same value, the determinant det(MiMTi). This value is a very important invariant of isomorphic graphs. We will, in Section 2.3, know what this invariant is.

Exercises: 1.10.4, 1.10.5, 1.10.6

1.10. MATRIX REPRESENTATION OF GRAPHS49

Exercises

1.10.6LetAbe the adjacency matrix of a graphG(undirected or directed). The

eigenvalues ofAis referred to as theeigenvaluesofG; the characteristic polynomial det(λI-A) is referred to as thecharacteristic polynomialof

G. Suppose that characteristic polynomial ofGis

P G(λ) = det(λI-A) =λv+c1λv-1+···+cv-1λ+cv. (a) Count the characteristic polynomials of the following two graphs. (Exercise 1.10.6) (b) Prove c k=?

H?Hk(-1)ω(H), k= 1,2,···,v,

whereHkis the set of (1-) 2-regular subgraphs with orderkof (di)graphs of G. (M.Milic (1964), H. Sachs (1964), L.Spialter (1964)) (c) Prove thatc1= 0;-c2=ε; and-c3is equal to twice the number of triangles inG. (d) Prove that ifλ1,λ2,···,λvare all eigenvalues ofG, then (i)λ1+λ2+···+λv=-c1; (ii) the number of different directed closedwalks of lengthkinG is (λk1+λk2+···+λkv). (e) Letλbe the maximum eigenvalue ofG. Prove that and the equalities hold if and only ifGis regular; (ii) ifGis strongly connected and regular, thenλhas the multiplicity 1. (f) Prove that a strongly connected digraph of diameterdhas at leatd+ 1 distinct eigenvalues.quotesdbs_dbs20.pdfusesText_26

[PDF] matrix row reduction

[PDF] matrix rref calculator wolfram

[PDF] matrix simultaneous equation calculator

[PDF] matrix solver

[PDF] matrix ti 89

[PDF] matrix vector multiplication c++

[PDF] mattydale bus schedule

[PDF] maurices credit card sign in comenity bank

[PDF] maury county tn school zoning map

[PDF] maury county tn zoning map

[PDF] max fg integrable

[PDF] max shred pdf

[PDF] max tutorial

[PDF] max tutorials for beginners

[PDF] max weber conflict theory