12nij12nij圖的矩陣表示圖是用三重組定的，可以用圖形表示。此外，可以用矩陣表示。使用矩陣表示，有利于用代數(shù)的法研究圖的性質(zhì)，也有利于使計(jì)算機(jī)對(duì)圖進(jìn)行處理。矩陣是研圖的重要工具之一。本主要討論無(wú)向圖和有向圖的鄰矩陣、有向圖的可達(dá)性矩陣、無(wú)圖的連通矩陣、無(wú)向圖有向圖的完全關(guān)聯(lián)矩陣。定義設(shè)G=個(gè)簡(jiǎn)單圖V…G)=()ij

n其中：

ij

到有邊到無(wú)邊或ijiji,j,n稱(chēng)A(G為G的鄰矩陣。簡(jiǎn)記為。例如圖9.22的接矩陣為：A(G)

0101

1011

0101

1110

又如圖9.23(a)的鄰接矩為：A(G)

0011

1010

0100

0110

由定義和以上兩例子容易看鄰接矩陣具有以下性質(zhì)：①鄰接矩陣的元全是或1這樣的矩陣叫布矩陣。鄰接矩陣是布爾矩陣。②無(wú)向圖的鄰接陣是對(duì)稱(chēng)陣，有向圖的鄰接矩不一定是對(duì)稱(chēng)陣。177/

1ijijijijijijijij2222ikkjikkjjjikkjjij23332222ikjj2223jijk-1k2③鄰接矩陣與結(jié)在圖中標(biāo)定次序有關(guān)圖9.23(a)鄰接矩陣是AG圖9.23(a)中的接點(diǎn)和的定序調(diào)換，得到圖，圖1ijijijijijijijij2222ikkjikkjjjikkjjij23332222ikjj2223jijk-1k2

0110

0011

1000

1010

考察(G和′()現(xiàn)，先將A(G的第一行與第二行對(duì)調(diào)，再將第一列與第二列對(duì)調(diào)得到A)。稱(chēng)A)AG)是置換等價(jià)。一般地說(shuō)，把n階方陣的某些行調(diào)，再把相應(yīng)的列做同樣的對(duì)，得到一個(gè)新的n階方陣A稱(chēng)A與A是換等價(jià)以明置換等價(jià)是n階布爾方陣集合上等價(jià)關(guān)系。雖然，對(duì)于同一圖，由于結(jié)點(diǎn)的標(biāo)定次序不同而得到不同的鄰接矩陣，但是這鄰接矩陣是置換等的。今后略去結(jié)點(diǎn)標(biāo)定次序的意性，取任意一個(gè)鄰接矩陣表示圖。④對(duì)有向圖來(lái)說(shuō)鄰接陣A(G)的第i行1個(gè)數(shù)是的度，第j列1的個(gè)數(shù)是ij的入度。⑤零圖的鄰接矩的元素全為零，叫做零矩陣。過(guò)來(lái)，如果一個(gè)圖的鄰接矩陣是矩陣，則此圖一定零圖。設(shè)向圖，V,…矩陣為A)12nijn若接矩陣的定義知v有一條邊v到有條長(zhǎng)度為路則到v無(wú)，即到無(wú)度為的路。故a表示從v到長(zhǎng)為1路的條數(shù)。

設(shè)=，A=(ij

)，按照矩陣乘法的定義，ij

ai1ji2j

in若a，則a=1且=1到有且v到v有邊，從而到viki

通過(guò)有一條度為2路；若aa，則a或a=0，v到v無(wú)邊或到無(wú)，因v到通過(guò)ikkjik無(wú)長(zhǎng)度為2的路k…。表示從到長(zhǎng)為2的路的條數(shù)。ijij設(shè)=AA，A=(a)，按照矩陣乘法的定義，ijaaijiji2jnj若≠則且≠0v到v有邊且到有由于是v到v長(zhǎng)為2ikikkj的路的條數(shù)表示到通v長(zhǎng)度的的條數(shù)aa=0,a=0，ikkjijikkjik則到無(wú)或v到v無(wú)長(zhǎng)度為的路，所以到v通無(wú)，=1,n。故表示從iij到v長(zhǎng)度3的路條數(shù)。ij……可以證明，這個(gè)論無(wú)向也成立。因此有下列定理成立。定理設(shè)(G是圖G的接矩陣(G(G)A(G

AG)

的第i行第j列素aij

等于從到v長(zhǎng)為的的條數(shù)。其中為v到身長(zhǎng)度為的路數(shù)。ijiii推論設(shè)Gn階單有向圖，是有向圖的接矩陣B＋A178/

＋…＋A

k，

k3234A00k3234A00A20012nij2nnnn

=()，則bijnnij

是G中v到v長(zhǎng)度小于等于的路的條數(shù)。是G中度小于ijijij等于的的總條。iii

是G中度小于等于k的回路數(shù)?！纠吭O(shè)G=E有向圖，圖形如圖，寫(xiě)出的接矩陣，出

2

，，A且確定到有少條長(zhǎng)度為3的到v有多少條長(zhǎng)度為的路v到自身長(zhǎng)12132度為和長(zhǎng)度為4的路各多解：鄰接矩陣A和A，，A如：

01

10

01

00

00

102

10

00

00

A

10

00

00

210

10

01

00

0

0

0

1

0

0

0

0

1

02

20

02

00

00

200

20

00

00

A

20

00

00

10

20

01

00

0

0

0

1

0

0

0

0

1

=2，以v到v長(zhǎng)度為的路有條它們分別是vv和v。232=1所以v到長(zhǎng)度為2的有：vv。133=0，v到自身無(wú)長(zhǎng)度為的回路。2=4v到自身有4條度回路，它們分別是vvv、vvvvv21232212和vv。212定義設(shè)=E有向圖，=v,,G)=(p)ijn其中：

ij=

到可達(dá)到不可達(dá)iji,j,稱(chēng)P(G為G的可性矩陣。簡(jiǎn)記為。在定義9.3.10規(guī)定了有向的任何結(jié)點(diǎn)自己和自己可達(dá)所可達(dá)性矩陣P(G)主對(duì)角線(xiàn)元素全為。設(shè)G=E階簡(jiǎn)單有向圖=,…達(dá)性矩陣的定義知，i≠j時(shí)如1果到v有，則=1；如果到v無(wú)，則p=0；又由定理知如果v到有路，ijijijijij則必存在長(zhǎng)度小等于1的。依據(jù)定理的論，如下計(jì)算圖G的達(dá)性矩陣：先計(jì)算BA＋A＋…＋，設(shè))。若b≠0則令p，若，nnijnijijij則令=0ij=1,,nij179/

0002-1nnn023=01(2)ii2in0(3)ijij再令i…0002-1nnn023=01(2)ii2in0(3)ijij令為階單位陣，則上述算法也以改進(jìn)為：計(jì)算=A＋B=＋＋A＋…＋，設(shè)=()。n–1n1ijnn若c≠0則令p，若=0，令=0，ij…。ijijijij使用上述方法，算例中G的達(dá)性矩陣，

43

37

33

00

00

11

11

11

00

00

=＋＋A＋A=4

3

30

40

03

1

10

10

01

01

0

0

0

1

3

0

0

0

1

1

計(jì)算簡(jiǎn)單有向圖G的可達(dá)性矩陣，可以用述方法：設(shè)是的接矩陣令A(yù)=()，ijn

()

=(a

(k)ij

)，n

0

為n階位。

=

，其ij

=(∧)∨(a∧a∧…∧(∧a)ij…,。iji2jinnj=，中(3)a∧)∨(∧)∧…∧∧a(2))ij…,nij1jjnj……=A∨A∨∨…

(n。其中運(yùn)算∨矩陣對(duì)應(yīng)元素的析取。可達(dá)性矩陣用來(lái)述有向圖的一個(gè)結(jié)點(diǎn)到另一個(gè)點(diǎn)是否有路，即是否可達(dá)。無(wú)向也可以用矩陣描述個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是否有路在無(wú)向圖中，如果結(jié)點(diǎn)之間有路稱(chēng)這兩個(gè)結(jié)點(diǎn)連通，不可達(dá)。所以把描述一個(gè)結(jié)點(diǎn)到一個(gè)結(jié)點(diǎn)是否有路的矩陣叫連通陣，而不叫可達(dá)性矩陣下面是無(wú)向圖連通矩陣的定義定義

設(shè)E無(wú)向圖=(G)=()ijn

,,12

其中：

ij

vv通ijvv連通iji,j…n稱(chēng)P(G為G的連矩陣。簡(jiǎn)記為。無(wú)向圖鄰接矩是對(duì)稱(chēng)陣無(wú)向圖連通矩也是對(duì)稱(chēng)陣求連通矩陣的方法可達(dá)性矩陣類(lèi)似。定義

設(shè)E圖，=MG)=()ij

,,…,,…1與e關(guān)聯(lián)其中：0否則i=1,…,，=1,…,稱(chēng)MG)為向圖的全聯(lián)矩陣。簡(jiǎn)記為M例如圖9.25的全關(guān)聯(lián)矩陣為：180/

1pij1pij0(G

10

設(shè)G=E向圖G的全關(guān)聯(lián)陣M(G)有以下的性：①每列元素之和為2。這說(shuō)明每條邊聯(lián)兩個(gè)結(jié)點(diǎn)。②每行元素之和對(duì)應(yīng)結(jié)點(diǎn)的度數(shù)。③所有元素之和圖中各結(jié)點(diǎn)度數(shù)的總和，也是數(shù)的2倍④兩列相同，則應(yīng)的兩個(gè)邊是平行邊。⑤某行元素全為，則對(duì)應(yīng)結(jié)點(diǎn)為孤立點(diǎn)。定義

設(shè)E圖，=(G)=(m)ijp

,,…,

e,…,12q其中：

ij

e始點(diǎn)ij是e終點(diǎn)v與e不聯(lián)iji=1,…,p，j=1,q稱(chēng)MG)為向圖的全聯(lián)矩陣。簡(jiǎn)記為M圖完全關(guān)聯(lián)矩陣為：MG

010設(shè)G=

E向圖G的完全關(guān)聯(lián)矩M)有以下的性質(zhì)：①每列有一個(gè)和一個(gè)1這說(shuō)明每條有向邊一始點(diǎn)和一個(gè)點(diǎn)。②每行個(gè)數(shù)是對(duì)應(yīng)結(jié)點(diǎn)的出度，的個(gè)數(shù)是對(duì)應(yīng)結(jié)點(diǎn)的。③所有元素之和，這說(shuō)明所有結(jié)點(diǎn)出度的和等于所有結(jié)點(diǎn)入度的和。④兩列相同，則應(yīng)的兩邊是平行邊。習(xí)

題

1.設(shè)

=E個(gè)簡(jiǎn)單向圖V=,v,

，鄰接矩陣如下：A)=

0011

1001010181/

⑴求v的出度deg⑵求v的入度deg()。⑶由v到長(zhǎng)度為2的有幾條？

10所以v1到v4長(zhǎng)為2的由條。2.向圖如圖所。⑴寫(xiě)出G的接矩陣。A=

110110

⑵根據(jù)鄰接矩陣求各結(jié)的出度和入度。degdeg

()deg()deg

(deg()=2((deg()=1(⑶求中長(zhǎng)度為的的總數(shù)，其中多少條回路。A3

共有8條，3回路。⑷求的

可達(dá)性矩陣。A133

2211

可達(dá)性矩陣

11111100⑸求的完全關(guān)聯(lián)矩陣M()

1010001001

182/

ijij⑹由完全關(guān)聯(lián)矩陣求各點(diǎn)的出度和入度。deg(v)ijijdeg(v)deg(vdeg(deg(v3.無(wú)向圖如圖9.28所示。⑴寫(xiě)出G的

鄰接矩陣。

⑵根據(jù)鄰接矩陣求各結(jié)的度數(shù)。v)deg()=3deg()=2⑶求中長(zhǎng)度為3的路的總數(shù)，其中有少條回路。

66,12⑷求的連通矩陣。G

11⑸求的完全關(guān)聯(lián)矩陣M()

⑹由完全關(guān)聯(lián)矩陣求各點(diǎn)的度數(shù)。vvdeg(vv4.設(shè)G=E個(gè)簡(jiǎn)單有向圖=…,

，=p)是圖的可達(dá)性矩陣，P=(p

)是

P的轉(zhuǎn)置矩陣。易知＝1表示到是可達(dá)的；p＝1表示到是可達(dá)的。因此∧1，ijijijjijiijijv和是互相可達(dá)的。由此可求得G的強(qiáng)分圖。例如G的可達(dá)性矩陣ij183/

P：

11P=10∧PP11P=10∧PP=1T

10

01

11

11

11

10

01

00

00

00

10

01