離散第9章圖論課件

第9章圖論9.1圖的基本概念9.2路和回路9.3連通圖9.4圖的矩陣表示9.5歐拉圖和漢密爾頓圖9.6樹9.7二部圖及匹配9.8返回總目錄第9章圖論

圖論是一個重要的數(shù)學(xué)分支。數(shù)學(xué)家歐拉1736年發(fā)表了關(guān)于圖論的第一篇論文，解決了著名的哥尼斯堡七橋問題?？讼；舴?qū)﹄娐肪W(wǎng)絡(luò)的研究、凱來在有機化學(xué)的計算中都應(yīng)用了樹和生成樹的概念。隨著科學(xué)技術(shù)的發(fā)展，圖論在運籌學(xué)、網(wǎng)絡(luò)理論、信息論、控制論和計算機科學(xué)等領(lǐng)域都得到廣泛的應(yīng)用。本章首先給出圖、簡單圖、完全圖、子圖、路和圖的同構(gòu)等概念，接著研究了連通圖性質(zhì)和規(guī)律，給出了鄰接矩陣、可達(dá)性矩陣、連通矩陣和完全關(guān)聯(lián)矩陣的定義。最后介紹了歐拉圖與哈密爾頓圖、樹、二部圖、平面圖和圖的著色。返回章目錄9.1圖的基本概念

9.1.1圖

兩個個體x，y的無序序列稱為無序?qū)?，記?x,y)。在無序?qū)?x,y)中，x，y是無序的，它們的順序可以顛倒，即(x,y)=(y,x)。定義9.1.1圖G是一個三重組V(G),E(G),G

其中：V(G)是非空結(jié)點集。

E(G)是邊集。

G是邊集到結(jié)點的有序?qū)驘o序?qū)系暮瘮?shù)。

由于在不引起混亂的情況下，圖的邊可以用有序?qū)驘o序?qū)χ苯颖硎尽Ｒ虼?，圖可以簡單的表示為：G=V,E其中：V是非空的結(jié)點集。E是邊的有序?qū)驘o序?qū)M成的集合。按照這種表示法，例9.1中的圖可以簡記為：G=V,E其中：V=a,b,c,dE=(a,b),(b,c),(a,c),(a,a)

定義9.1.2

若圖G有n個結(jié)點，則稱該圖為n階圖。定義9.1.3

設(shè)G為圖，如果G的所有邊都是有向邊，則稱G為有向圖。如果G的所有邊都是無向邊，則稱G為無向圖。如果G中既有有向邊，又有無向邊，則稱G為混合圖。圖9.3的(a)是無向圖，(b)是有向圖，(c)是混合圖。

在一個圖中，若兩個結(jié)點由一條邊(有向邊或無向邊)關(guān)聯(lián)，則稱其中的一個結(jié)點是另一個結(jié)點的鄰接點。并稱這兩個結(jié)點相互鄰接。在一個圖中不與任何結(jié)點相鄰接的結(jié)點，稱為孤立點。在一個圖中，如果兩條邊關(guān)聯(lián)于同一個結(jié)點，則稱其中的一個邊是另一個邊的鄰接邊。并稱這兩個邊相互鄰接。關(guān)聯(lián)于同一個結(jié)點的一條邊叫做環(huán)或自回路。在有向圖中環(huán)的方向可以是順時針，也可以是逆時針，它們是等效的。定義9.1.4

由孤立點組成的圖叫做零圖。由一個孤立點組成的圖叫做平凡圖。根據(jù)定義9.1.4，平凡圖一定是零圖。

定理9.1.1在任何圖G=V,E中，所有結(jié)點度數(shù)的和等于邊數(shù)的2倍。即：=2|E|證明：圖的每一條邊都和兩個結(jié)點相關(guān)聯(lián)，為每個相關(guān)聯(lián)的結(jié)點增加一度,給圖增加兩度。所以所有結(jié)點度數(shù)的和等于邊數(shù)的2倍。推論

在任何圖G=V,E中，度數(shù)為奇數(shù)的結(jié)點必為偶數(shù)個。定義9.1.6

設(shè)G=V,E是有向圖，vV，射入(出)結(jié)點v的邊數(shù)稱為結(jié)點v的入(出)度。記為deg－(v)(deg＋(v))。顯然，任何結(jié)點的入度與出度的和等于該結(jié)點的度數(shù)，即deg(v)=deg－(v)+deg＋(v)。定理9.1.2在有向圖中，所有結(jié)點入度的和等于所有結(jié)點出度的和。證明：在有向圖中每一條邊對應(yīng)一個入度和一個出度，為圖的入度和出度各增加1。所以，所有結(jié)點入度的和等于邊數(shù)，所有結(jié)點出度的和也等于邊數(shù)。

9.1.3多重圖、簡單圖、完全圖和正則圖定義9.1.7在圖G中，連接同一對結(jié)點的多條相同邊稱為平行邊。平行邊的條數(shù)稱為該平行邊的重數(shù)。含平行邊的圖叫多重圖。不含平行邊和環(huán)的圖叫簡單圖。例如，在圖9.4(a)中結(jié)點a和b之間有兩條平行邊，結(jié)點b和c之間有三條平行邊，結(jié)點b上有兩條平行邊，這兩條平行邊都是環(huán)。圖9.4(a)不是簡單圖。又如，在圖9.4(b)中結(jié)點v1和v2之間有兩條平行邊。v2和v3之間的兩條邊，因為方向不同，所以不是平行邊。圖9.4(b)不是簡單圖。簡單圖不含平行邊和環(huán)。

定理9.1.3設(shè)G為n階簡單無向圖，則(G)≤n–1。證明：因為G有n個結(jié)點，G的任何結(jié)點v最多只能與其余的n–1結(jié)點相鄰接；又因為G為簡單圖，既無平行邊，又無環(huán)。所以deg(v)≤n–1。由v的任意性，就有

(G)=maxdeg(v)|vV≤n–1。定義9.1.8

設(shè)G為n階簡單無向圖，若G中的每個結(jié)點都與其余的n–1個結(jié)點相鄰接，則稱G為n階無向完全圖。記為Kn。在n階無向完全圖中，給每一條邊任意確定一個方向，所得到的圖稱為n階有向完全圖。也記為Kn。

今后，將n階無向完全圖和n階有向完全圖統(tǒng)稱為n階完全圖。

定理9.1.4

n階完全圖Kn的邊數(shù)為證明：在Kn中，每個結(jié)點都與其余的n–1結(jié)點相鄰接，即任何一對結(jié)點之間都有一條邊，故邊數(shù)應(yīng)為

定義9.1.9

設(shè)G為n階簡單無向圖，若G中每個結(jié)點都是k度的，則稱G為k次正則圖。

9.1.4圖的同構(gòu)在圖論中只關(guān)心結(jié)點間是否有連線，而不關(guān)心結(jié)點的位置和連線的形狀。因此，對于給定的圖而言，如果將圖的各結(jié)點安排在不同的位置上，并且用不同形狀的弧線或直線表示各邊，則可以得到各種不同圖形。所以，同一圖的圖形并不惟一。由于這種圖形表示的任意性，可能出現(xiàn)這樣的情況：看起來完全不同的兩種圖形，卻表示著同一個圖。例如，在圖9.6中，(a)和(b)兩個圖的圖形不同，但它們的結(jié)構(gòu)完全相同，是同一個圖。為了描述看起來不同，而其結(jié)構(gòu)完全相同的圖，引入了同構(gòu)的概念。

定義9.1.10

設(shè)G1=V1,E1與G2=V2,E2是兩個無向圖(有向圖)，若存在雙射函數(shù)f：V1V2，v1V1，v2V1(v1,v2)E1(v1,v2E1)當(dāng)且僅當(dāng)(f(v1),f(v2))E2)(f(v1),f(v2)E2)并且(v1,v2)(v1,v2)與(f(v1),f(v2))(f(v1),f(v2))的重數(shù)相同，則稱圖G1與圖G2同構(gòu)。記為G1≌G2。雙射函數(shù)f稱為圖G1與圖G2的同構(gòu)函數(shù)。

兩個圖同構(gòu)必須滿足下列條件：①結(jié)點數(shù)相同。②邊數(shù)相同。③度數(shù)相同的結(jié)點數(shù)相同。這三個條件是兩個圖同構(gòu)的必要條件，不是充分條件。一般的，用上述三個必要條件判斷兩個圖是不同構(gòu)的。兩個圖同構(gòu)，它們的同構(gòu)函數(shù)必須實現(xiàn)同度結(jié)點對應(yīng)同度結(jié)點。

9.1.5補圖、子圖和生成子圖定義9.1.11設(shè)G=V,E是n階簡單無向圖，G中的所有結(jié)點和所有能使G成為完全圖的添加邊組成的圖稱為圖G的相對于完全圖的補圖，簡稱為G的補圖。記為。若G≌，則稱G為自補圖。

在圖9.9中，(b)是(a)的補圖，(a)與(b)同構(gòu)，所以(a)是自補圖。

9.2

路和回路定義9.2.1設(shè)G=V,E是圖，G中的結(jié)點與邊的交替序列L：v0e1v1e2v2…envn叫做v0到vn的路。其中vi-1與vi是ei的端點，i=1,…,n。v0和vn分別叫做路L的始點和終點。路L中邊的條數(shù)叫做該路的長度。例如，在圖9.11中，L1：v5e8v4e5v2e6v5e7v3是從v5到v3的路，v5是始點，v3是終點，長度為4。L2：v1e1v2e3v3是從v1到v3的路，v1是始點，v3是終點，長度為2。在簡單圖中沒有平行邊和環(huán)，路L：v0e1v1e2v2…envn完全由它的結(jié)點序列v0v1v2…vn確定。所以，在簡單圖中的路可以用結(jié)點序列表示。

定義9.2.2設(shè)G=V,E是圖，L是從

v0到vn的路。若v0=vn，則稱L為回路。若L中所有邊各異，則稱L為簡單路。若此時又有v0=vn，則稱L為簡單回路。若L中所有結(jié)點各異，則稱L為基本路。若此時又有v0=vn，則稱L為基本回路。若L既是簡單路，又是基本路，則稱L為初級路。若此時又有v0=vn，則稱L為初級回路。

在圖9.11中，L1是一條簡單路。L2是一條簡單路、基本路、初級路。。定理9.2.1

在n階圖G中，若從結(jié)點vi到vj(vi≠vj)存在一條路，則必存在長度小于等于n-1的路。證明：設(shè)L：vie1v1e2v2…ejvj是G中一條從結(jié)點vi到vj長度為l的路，路上有l(wèi)+1個結(jié)點。若l≤n-1，則定理已證。否則，l＞n-1，此時，l+1＞n，即路L上的結(jié)點數(shù)l+1大于圖G中的結(jié)點數(shù)n，此路上必有相同結(jié)點。設(shè)vk和vs相同。于是，此路兩次通過同一個結(jié)點vk(vs)，所以在L上存在vs到自身的回路Cks。在L上刪除Cks上的一切邊和除vs以外的一切結(jié)點，得路L1：vie1v1…ekvs…ejvj。L1仍為從結(jié)點vi到vj的路，且長度至少比L減少1。若路L1的長度小于等于n-1，則定理已證。否則，重復(fù)上述過程。由于G有n個結(jié)點，經(jīng)過有限步后，必得到從vi到vj長度小于等于n-1的路。9.3連通圖9.3.1無向連通圖定義9.3.1在無向圖G中，如果結(jié)點u和結(jié)點v之間存在一條路，則稱結(jié)點u和結(jié)點v連通。記為u～v。規(guī)定，G中任意結(jié)點v和自身連通，即v～v。在無向圖中，如果結(jié)點u和結(jié)點v連通，即u～v，那么，結(jié)點v和結(jié)點u連通，即v～u。所以，無向圖結(jié)點間的連通是對稱的。設(shè)G=V,E是無向圖，在圖G的結(jié)點集V上建立一個二元關(guān)系R：R=u,v|uV∧vV∧u和v連通R叫做無向圖G的結(jié)點集V上的連通關(guān)系。因為R是自反的、對稱的、傳遞的，所以R是V上的等價關(guān)系。無向圖G的結(jié)點集V上的連通關(guān)系是等價關(guān)系。設(shè)G是圖9.14。結(jié)點集V上的連通關(guān)系為R，以下驗證R是V上的等價關(guān)系，并找出所有等價類。

R=a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c,d,d,e,e,e,f,e,g,e,h,f,e,f,f,f,g,f,h,g,e,g,f,g,g,g,h,h,e,h,f,h,g,h,h=a,b,c×a,b,c∪d×d∪e,f,g,h×e,f,g,h根據(jù)定義，R是V上的等價關(guān)系。等價類有三個，分別是：a,b,c，d，e,f,g,h。定義9.3.4

設(shè)G=V,E是無向圖，

R是V上的連通關(guān)系，V/R=ViVi是R的等價類，i=1,…,k

是V關(guān)于R的商集，G[Vi]是Vi導(dǎo)出的子圖，稱G[Vi](i=1,…,k)為G的連通分支。G的連通分支數(shù)記為W(G)。

設(shè)圖9.14為G，在G中，連通關(guān)系R的三個等價類是a,b,c，d，e,f,g,h

，它們導(dǎo)出的G的子圖分別是圖9.14中的(a)，(b)，(c)。它們都是G的連通分支。G的連通分支數(shù)W(G)=3。每一個連通分支中任何兩個結(jié)點是連通的，而位于不同連通分支中的任何兩個結(jié)點是不連通的。即每一個連通分支都是原圖的最大的連通子圖。在圖9.14中，(a)，(b)，(c)都是最大的連通子圖。

定義9.3.5設(shè)u，v是無向圖G中的任意兩個結(jié)點，若u和v連通，則u和v之間最短路的長叫做結(jié)點u與結(jié)點v的距離，記為d(u,v)。若u和v不連通，規(guī)定，u與v的距離為∞。即d(u,v)=∞。設(shè)G=V,E是無向圖，u、v和w是V中的任意結(jié)點，G的結(jié)點間的距離有以下的性質(zhì)：①d(u,v)≥0②d(u,u)=0③d(u,v)＋d(v,w)≥d(u,w)④d(u,v)=d(v,u)在n階無向完全圖Kn中，每兩個不同結(jié)點間都有一條邊，它們的距離是1。在零圖中，每兩個不同結(jié)點間都沒有路，它們的距離都是∞。在圖G中刪除一個結(jié)點，就是將這個結(jié)點與它的所有關(guān)聯(lián)邊全部刪除。刪除一個邊，則僅去掉這個邊。

定義9.3.6

設(shè)G=V,E是無向連通圖，V1V且V1≠?，滿足：⑴刪除V1的所有結(jié)點，得到的子圖是不連通的。⑵刪除V1的任何真子集，得到的子圖是連通的。則稱V1是G的點割集。如果某一個結(jié)點組成了點割集，則稱該點為割點。

在圖9.16中，b,d，c，e都是點割集，結(jié)點c和結(jié)點e都是割點。雖然刪除結(jié)點a和c圖成為不連通的，但因c是a,c的真子集，所以a,c不是點割集。定義9.3.7設(shè)G=V,E是無向連通圖，如果G不是完全圖，k(G)=min|V1|V1是G的點割集稱為圖G的點連通度。如果G是完全圖，規(guī)定n階無向完全圖Kn的點連通度為n–1，即k(Kn)=n–1。規(guī)定不連通圖G的點連通度為0。即k(G)=0。圖9.16是無向連通圖，但不是完全圖，存在割點c和e，所以點連通度是1。

無向連通圖的點連通度的物理意義是：要使G成為不連通的最少要刪除的結(jié)點數(shù)。圖9.16的點連通度是1，最少刪除一個結(jié)點，圖成為不連通的，例如刪除結(jié)點c或結(jié)點e。

定義9.3.8

設(shè)G=V,E是無向連通圖，E1E且E1≠?，滿足：⑴刪除E1的所有邊，得到的子圖是不連通的。⑵刪除E1的任何真子集，得到的子圖是連通的。則稱E1是G的邊割集。如果某一條邊組成了邊割集，則稱該邊為割邊或橋。在圖9.16中，集合(c,e)、(e,f)、(a,b),(d,c)和(a,d),(b,c)都是G的邊割集，無向邊(c,e)和(e,f)為割邊。雖然刪除邊(a,d)、(a,b)和(d,c)圖成為不連通的，但因集合(a,b),(d,c)是集合(a,d),(a,b),(d,c)的真子集，所以(a,d),(a,b),(d,c)不是邊割集。定義9.3.9

設(shè)G=V,E是無向連通圖，如果G是非平凡圖，(G)=min|E1|E1是G的邊割集稱為G的邊連通度。如果G是平凡圖，規(guī)定G的邊連通度為0。規(guī)定不連通圖G的邊連通度為0，即(G)=0。圖9.16是無向連通圖，但不是平凡圖，存在割邊(c,e)和(e,f)，所以，它的邊連通度是1。無向連通圖的邊連通度的物理意義是：要使G成為不連通的最少要刪除的邊數(shù)。圖9.16的邊連通度是1，最少刪除一條邊，圖就會成為不連通的，例如刪除割邊(c,e)或(e,f)。無向圖G的點連通度k(G)、邊連通度(G)和最小度

(G)有下列的關(guān)系：

定理9.3.1

設(shè)G=V,E為任意無向圖，則k(G)≤(G)≤

(G)證明：⑴如果G是不連通的，由點連通度和邊連通度的定義有k(G)=(G)=0，所以k(G)≤(G)≤(G)⑵如果G是連通圖。①先證明(G)≤

(G)如果G是平凡圖，(G)=0≤(G)，即(G)≤

(G)如果G是非平凡圖，設(shè)n=(G)=mindeg(v)|vV，則存在G的一個結(jié)點v，它關(guān)聯(lián)了n條邊，而其它結(jié)點關(guān)聯(lián)的邊數(shù)大于等于n，將v關(guān)聯(lián)的這n條邊刪除，G成為不連通的。從而這n條邊或這n條邊中的幾條邊組成一個邊割集，即存在一個邊割集的基數(shù)小于等于n，所以min|E1||E1是G的邊割集≤n=mindeg(v)|vV

，即(G)≤(G)②再證k(G)≤(G)設(shè)(G)=1，G有一條割邊，此邊的任一端點是割點，k(G)=1。所以k(G)≤(G)成立。設(shè)(G)≥2，則可刪除某(G)條邊，使G成為不連通的，而刪除其中的(G)–1條邊，它仍然是連通的且有一個橋，設(shè)該橋為e=(u,v)。對這(G)–1條邊選取一個不同于u，也不同于v的端點，把這些端點刪除，則必至少刪除了這(G)–1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)≤(G)–1≤(G)。若這樣產(chǎn)生的圖是連通的，則e=(u,v)仍是橋。此時再刪除u或v，就必產(chǎn)生了一個不連通圖，故k(G)≤(G)由⑴和⑵得k(G)≤(G)≤(G)圖9.17是無向連通圖，點連通度k(G)=1，邊連通度(G)=2，最小度(G)=3，此圖滿足k(G)≤(G)≤(G)。定理9.3.2在無向連通圖G中，結(jié)點v是割點的充分必要條件是存在兩個結(jié)點u和w，使結(jié)點u和w之間的每一條路都通過v。證明：設(shè)v是割點，證明存在兩個結(jié)點u和w，使結(jié)點u和w之間的每一條路都通過v。v是割點，刪除v得G′，G′至少包含兩個連通分支，設(shè)其中的兩個為G1=V1,E1和G2=V2,E2，uV1，wV2，因為G連通，在G中u和w之間必有路，設(shè)L是它們之間任意一條路。在G′中，由于u和w屬于兩個不同連通分支，所以，u和w之間必沒有路。故L必通過v。設(shè)存在兩個結(jié)點u和w，使結(jié)點u和w之間的每一條路都通過v，證明v是割點。刪除v得子圖G′，因為結(jié)點u和w之間的每一條路都通過v，所以在G′中結(jié)點u和w之間必?zé)o路，即結(jié)點u和w不連通。由連通圖的定義知，G′是不連通的，故v是G的割點。

9.3.2有向連通圖定義9.3.10

在有向圖G中，結(jié)點u到結(jié)點v存在一條路，則稱結(jié)點u到結(jié)點v可達(dá)。記為u→v。如果u到v可達(dá)且v到u也可達(dá)，稱結(jié)點u和結(jié)點v相互可達(dá)。記為u?v。規(guī)定，G中任何結(jié)點v自己到自己可達(dá)，即v?v。定義9.3.11

在有向圖G=V,E中，uV，vV，若結(jié)點u到結(jié)點v可達(dá)，u到v最短路的長稱為結(jié)點u到結(jié)點v的距離。記為du,v。若u到v不可達(dá)，規(guī)定，u到v的距離為∞。即du,v=∞。對于有向圖G中的任意結(jié)點u,v和w，結(jié)點間的距離有以下的性質(zhì)：①du,v≥0②du,u=0③du,v＋dv,w≥du,w

定義9.3.12在簡單有向圖G中，對于任意兩個結(jié)點u和v，⑴如果結(jié)點u到結(jié)點v可達(dá)或結(jié)點v到結(jié)點u可達(dá)，則稱G為單向(側(cè))連通的。⑵如果結(jié)點u和結(jié)點v互相可達(dá)，則稱G為強連通的。⑶如果略去方向得到的無向圖是連通的，則稱G為弱連通的。在圖9.18中，(a)是強連通的、單向(側(cè))連通的和弱連通的。(b)是單向(側(cè))連通的和弱連通的，但不是強連通的。(c)是弱連通的，但不是單向(側(cè))連通的，也不是強連通的。一般地說，若有向圖G是強連通的，則必是單向(側(cè))連通的和弱連通的；若有向圖G是單向(側(cè))連通的，則必是弱連通的。反之不真。

定理9.3.3一個有向圖G是強連通的充分必要條件是G中有一個回路至少包含G的每個結(jié)點一次。證明：設(shè)G中有一個回路至少包含G的每個結(jié)點一次，下證G是強連通的。G中有一個回路至少包含每個結(jié)點一次，則G中的任意兩個結(jié)點通過回路互相可達(dá)。所以G是強連通的。設(shè)G是強連通的，下證G中有一個回路至少包含G的每個結(jié)點一次。若不然，存在結(jié)點v不在G的任何回路上，則v與其它任何結(jié)點不能互相可達(dá)，這與G是強連通的矛盾。故G中有一個回路至少包含G的每個結(jié)點一次。定理9.3.4

一個有向圖G是單向連通的充分必要條件是G中有一個路至少包含每個結(jié)點一次。證明略。定義9.3.13

在簡單有向圖G中，具有強(單向，弱)連通性質(zhì)的最大子圖叫做強(單向，弱)分圖。在圖9.19(a)中，由v1,v2,v3,v4導(dǎo)出的子圖是強分圖，v5導(dǎo)出的子圖也是強分圖。由v1,v2,v3,v4,v5導(dǎo)出的子圖是單向分圖，也是弱分圖。在圖9.19(b)中，v1，v2，v3，v4導(dǎo)出的子圖是強分圖，v1,v2,v3，和v1,v3,v4導(dǎo)出的子圖是單向分圖，v1,v2,v3,v4導(dǎo)出了弱分圖。

定理9.3.5在有向圖G=V,E中，每一個結(jié)點位于且只位于一個強分圖中。證明：⑴vV，令V1是G中所有與v互相可達(dá)的結(jié)點組成的集合，當(dāng)然vV1，V1導(dǎo)出的子圖是G的強分圖。故G的每一個結(jié)點位于一個強分圖中。⑵設(shè)G1=V1,E1和G2=V2,E2是G的兩個強分圖，設(shè)vV1且vV2，則v與G1中的所有結(jié)點相互可達(dá)且與G2中的所有結(jié)點相互可達(dá)。于是G1中的結(jié)點與G2中的結(jié)點通過v相互可達(dá)。這與G1和G2是強分圖相矛盾。故G的每一個結(jié)點只位于一個強分圖中。

返回章目錄9.4圖的矩陣表示定義9.4.1設(shè)G=V,E是一個簡單圖，V=v1,v2,…,vn

A(G)=(aij)

n×n其中：i,j=1,…,n稱A(G)為G的鄰接矩陣。簡記為A。

例如圖9.22的鄰接矩陣為：

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

鄰接矩陣具有以下性質(zhì)：①鄰接矩陣的元素全是0或1。這樣的矩陣叫布爾矩陣。鄰接矩陣是布爾矩陣。②無向圖的鄰接矩陣是對稱陣，有向圖的鄰接矩陣不一定是對稱陣。③鄰接矩陣與結(jié)點在圖中標(biāo)定次序有關(guān)。例如圖9.23(a)的鄰接矩陣是A(G)，若將圖9.23(a)中的接點v1和v2的標(biāo)定次序調(diào)換，得到圖9.23(b)，圖9.23(b)的鄰接矩陣是A′(G)。考察A(G)和A′(G)發(fā)現(xiàn)，先將A(G)的第一行與第二行對調(diào)，再將第一列與第二列對調(diào)可得到A′(G)。稱A′(G)與A(G)是置換等價的。一般地說，把n階方陣A的某些行對調(diào)，再把相應(yīng)的列做同樣的對調(diào)，得到一個新的n階方陣A′，則稱A′與A是置換等價的。可以證明置換等價是n階布爾方陣集合上的等價關(guān)系。雖然，對于同一個圖，由于結(jié)點的標(biāo)定次序不同，而得到不同的鄰接矩陣，但是這些鄰接矩陣是置換等價的。今后略去結(jié)點標(biāo)定次序的任意性，取任意一個鄰接矩陣表示該圖。④對有向圖來說，鄰接矩陣A(G)的第i行1的個數(shù)是vi的出度，第j列1的個數(shù)是vj的入度。⑤零圖的鄰接矩陣的元素全為零，叫做零矩陣。反過來，如果一個圖的鄰接矩陣是零矩陣，則此圖一定是零圖。

定理9.4.1設(shè)A(G)是圖G的鄰接矩陣，A(G)k=A(G)A(G)k-1，A(G)k的第i行，第j列元素等于從vi到vj長度為k的路的條數(shù)。其中為vi到自身長度為k的回路數(shù)。

推論設(shè)G=V,E是n階簡單有向圖，A是有向圖G的鄰接矩陣，Bk=A＋A2＋…＋Ak，Bk=()n×n，則是G中由vi到vj長度小于等于k的路的條數(shù)。是G中長度小于等于k的路的總條數(shù)。是G中長度小于等于k的回路數(shù)?！纠?.4】設(shè)G=V,E為簡單有向圖，圖形如圖9.24，寫出G的鄰接矩陣A，算出A2，A3，A4且確定v1到v2有多少條長度為3的路?v1到v3有多少條長度為2的路?v2到自身長度為3和長度為4的回路各多少條?

解：鄰接矩陣A和A2，A3，A4如下：

=2，所以v1到v2長度為3的路有2條，它們分別是：v1v2v1v2和v1v2v3v2。=1，所以v1到v3長度為2的路有1條：v1v2v3。=0，v2到自身無長度為3的回路。=4，v2到自身有4條長度為4的回路，它們分別是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。定義9.4.2設(shè)G=V,E是簡單有向圖，V=v1,v2,…,vn

P(G)=(pij)n×n其中：pij

=i,j=1,…,n稱P(G)為G的可達(dá)性矩陣。簡記為P。在定義9.3.10中，規(guī)定了有向圖的任何結(jié)點自己和自己可達(dá)。所以可達(dá)性矩陣P(G)的主對角線元素全為1。設(shè)G=V,E是n階簡單有向圖，V=v1,v2,…,vn，由可達(dá)性矩陣的定義知，當(dāng)i≠j時，如果vi到vj有路，則pij=1；如果vi到vj無路，則pij=0；又由定理9.2.1知，如果vi到vj有路，則必存在長度小于等于n–1的路。依據(jù)定理9.4.1的推論，如下計算圖G的可達(dá)性矩陣P：先計算Bn–1=A＋A2＋…＋An–1，設(shè)Bn–1=()n×n。若≠0，則令pij=1，若=0，則令pij=0，i,j=1,…,n。再令pii=1，i=1,…,n。就得到了圖G的可達(dá)性矩陣P。令A(yù)0為n階單位陣，則上述算法也可以改進(jìn)為：計算Cn–1=A0＋Bn–1=A0＋A＋A2＋…＋An-1，設(shè)Cn–1=()n×n。若≠0，則令pij=1，若=0，則令pij=0，i,j=1,…,n。使用上述方法，計算例9.4中圖G的可達(dá)性矩陣，

C4=A0＋A＋A2＋A3＋A4=

P=計算簡單有向圖G的可達(dá)性矩陣P，還可以用下述方法：設(shè)A是G的鄰接矩陣，令A(yù)=(aij)n×n，A(k)=()n×n，A0為n階單位陣。A(2)=A°A，其中=(ai1∧a1j)∨(ai2∧a2j)∨…∨(ain∧anj)i,j=1,…,n。A(3)=A°A(2)，其中(ai1∧)∨…∨(ain∧)

i,j=1,…,n?！璓=A0∨A∨A(2)∨A(3)∨…∨A(n–1)。其中，運算∨是矩陣對應(yīng)元素的析取。可達(dá)性矩陣用來描述有向圖的一個結(jié)點到另一個結(jié)點是否有路，即是否可達(dá)。無向圖也可以用矩陣描述一個結(jié)點到另一個結(jié)點是否有路。在無向圖中，如果結(jié)點之間有路，稱這兩個結(jié)點連通，不叫可達(dá)。所以把描述一個結(jié)點到另一個結(jié)點是否有路的矩陣叫連通矩陣，而不叫可達(dá)性矩陣。

定義9.4.3設(shè)G=V,E是簡單無向圖，V=v1,v2,…,vnP(G)=(pij)

n×n其中：i,j=1,…,n稱P(G)為G的連通矩陣。簡記為P。無向圖的鄰接矩陣是對稱陣，無向圖的連通矩陣也是對稱陣。求連通矩陣的方法與可達(dá)性矩陣類似。

定義9.4.4設(shè)G=V,E是無向圖，V=v1,v2,…,vp，E=e1,e2,…,eqM(G)=(mij)

p×q其中：

i=1,…,p，j=1,…,q稱M(G)為無向圖G的完全關(guān)聯(lián)矩陣。簡記為M。

例如圖9.25的完全關(guān)聯(lián)矩陣為：

M(G)=

設(shè)G=V,E是無向圖，G的完全關(guān)聯(lián)矩陣M(G)有以下的性質(zhì)：①每列元素之和均為2。這說明每條邊關(guān)聯(lián)兩個結(jié)點。②每行元素之和是對應(yīng)結(jié)點的度數(shù)。③所有元素之和是圖各結(jié)點度數(shù)的和，也是邊數(shù)的2倍。④兩列相同，則對應(yīng)的兩個邊是平行邊。⑤某行元素全為零，則對應(yīng)結(jié)點為孤立點。

定義9.4.5設(shè)G=V,E是有向圖，V=v1,v2,…,vp，E=e1,e2,…,eq

M(G)=(mij)

p×q其中：i=1,…,p，j=1,…,q

稱M(G)為有向圖G的完全關(guān)聯(lián)矩陣。簡記為M。

圖9.26的完全關(guān)聯(lián)矩陣為：

M(G)=

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

返回章目錄9.5歐拉圖和漢密爾頓圖

9.5.1歐拉圖定義9.5.1

在無孤立結(jié)點的圖G(有向圖或無向圖)中，如果存在一條路經(jīng)過每一條邊一次且僅一次，則稱該路為歐拉路。如果存在一條回路經(jīng)過每一條邊一次且僅一次，則稱該回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖。定理9.5.1無向圖G具有一條歐拉路當(dāng)且僅當(dāng)G是連通的且有零個或兩個奇度結(jié)點。證明：設(shè)G具有一條歐拉路，下證G是連通的且有零個或兩個奇度結(jié)點。設(shè)G中有一條歐拉路L：v0e1v1e2v2…ekvk，該路經(jīng)過G的每一條邊。因為G中無孤立結(jié)點，所以該路經(jīng)過G的所有結(jié)點，即G的所有結(jié)點都在該路上。故G中任意兩個結(jié)點連通，從而G是連通圖。設(shè)vi是圖G的任意結(jié)點，若vi不是L的端點，每當(dāng)沿L經(jīng)過vi一次都經(jīng)過該結(jié)點關(guān)聯(lián)的兩條邊，為該結(jié)點的度數(shù)增加2。由于G的每一條邊都在該路上，且不重復(fù)，所以vi的度數(shù)必為偶數(shù)。若vi是L的端點v0，當(dāng)v0=vk時，則v0和vk的度數(shù)也為偶數(shù)，即G中無奇度結(jié)點；當(dāng)v0≠vk時，則v0和vk的度數(shù)均為奇數(shù)，即G中有兩個奇度結(jié)點。設(shè)G是連通的且有零個或兩個奇度結(jié)點，下證G具有一條歐拉路。設(shè)G是連通圖，有零個或兩個奇度結(jié)點，用下述方法構(gòu)造一條歐拉路：①若G中有兩個奇度結(jié)點，則從其中的一個v0開始構(gòu)造一條簡單路。從v0出發(fā)經(jīng)關(guān)聯(lián)邊e1進(jìn)入v1，若v1是偶數(shù)度結(jié)點，則必可以由v1經(jīng)關(guān)聯(lián)邊e2進(jìn)入v2。如此下去，每邊只取一次。由于G是連通圖，必可到達(dá)另一個奇度結(jié)點vk，從而得到一條簡單路L1：v0e1v1e2v2…ekvk。若G中無奇度結(jié)點，則從任意結(jié)點v0出發(fā)，用上述方法必可回到結(jié)點v0，得到一條簡單回路L1：v0e1v1e2v2…v0。②若L1經(jīng)過G的所有邊，則L1就是歐拉路。③否則，在G中刪除L1，得子圖G′，則G′中的每一個結(jié)點的度數(shù)為偶數(shù)。因為G是連通圖，故L1和G′至少有一個結(jié)點vi重合，在G′中由vi出發(fā)重復(fù)①，得到簡單回路L2。④若L1與L2組合在一起恰是G，則得到了歐拉路，否則，重復(fù)③可得到簡單回路L3。以此類推直到得到一條經(jīng)過G中所有邊的歐拉路。

推論無向圖G具有一條歐拉回路當(dāng)且僅當(dāng)G是連通的且所有結(jié)點都是偶度的。這個推論說明，無向圖G是歐拉圖當(dāng)且僅當(dāng)G是連通的且所有結(jié)點都是偶度的。圖9.30(a)的每一個結(jié)點的度數(shù)都是偶數(shù)2，所以(a)中有一個歐拉回路，是歐拉圖；在圖9.30(b)中有兩個結(jié)點的度數(shù)是奇數(shù)3，故(b)中有一個歐拉路，但沒有歐拉回路，不是歐拉圖；在圖9.30(c)中四個結(jié)點的度數(shù)都是奇數(shù)3，(c)中沒有歐拉路，更沒有歐拉回路，不是歐拉圖。

定理9.5.2有向圖G具有一條歐拉回路當(dāng)且僅當(dāng)G是強連通的且每個結(jié)點的入度等于出度。這個定理說明，有向圖G是歐拉圖的充分必要條件是G是強連通的且每個結(jié)點的入度等于出度。定理9.5.3有向圖G具有一條歐拉路當(dāng)且僅當(dāng)G是單向連通的且除了兩個結(jié)點外，每個結(jié)點的入度等于出度，而在這兩個結(jié)點中，一個結(jié)點入度比出度大1，另一個結(jié)點入度比出度小1。

這兩個定理可以看作定理9.5.1和推論的推廣。因為對于有向圖的任意一個結(jié)點，如果入度與出度相等，則該結(jié)點的度數(shù)為偶數(shù)。若入度與出度之差為1時，則該結(jié)點的度數(shù)為奇數(shù)。因此定理9.5.2和定理9.5.3的證明與定理9.5.1的證明類似。

圖9.31(a)是強連通的且每一個結(jié)點的入度等于出度，都等于1，所以(a)中有一個歐拉回路，是歐拉圖；圖9.31(b)是單向連通的且有兩個結(jié)點入度與出度相等，有兩個結(jié)點入度與出度不相等，其中一個結(jié)點入度比出度大1，另一個結(jié)點入度比出度小1。故有一個歐拉路，但沒有歐拉回路，不是歐拉圖；圖9.31(c)的四個結(jié)點入度與出度都不相等，沒有歐拉路，更沒有歐拉回路。

哥尼斯堡七橋問題從前，一個稱為哥尼斯堡城的城市有一條橫貫全市的普雷格爾河，河中有兩個小島，用七座橋?qū)u和島，河岸和島連接起來，如圖9.32所示。18世紀(jì)中葉，該城市的人們提出了一個問題：能否不重復(fù)的走完七橋，最后回到原地。城中的很多人試圖解決這個問題，然而試驗者都以失敗告終。1736年瑞士的數(shù)學(xué)家列昂哈德?歐拉(LeonhardEuler)發(fā)表了一篇論文《哥尼斯堡七橋問題》，這篇論文的基本內(nèi)容就是定理9.5.1。在這篇論文中第一次論證了這個問題是無解的。他將河岸和島抽象成圖的結(jié)點，而把橋畫成相應(yīng)的連接邊，如圖9.33所示。于是，不重復(fù)的走完七橋，最后回到原地，等價于圖中存在一條回路，經(jīng)過每一條邊一次且僅一次，即圖中存在歐拉回路。因為圖中的四個結(jié)點的度數(shù)都是奇數(shù)。所以圖中不存在歐拉回路。9.5.2漢密爾頓圖一個與歐拉回路和歐拉圖非常類似的問題是漢密爾頓回路和漢密爾頓圖問題。它是由愛爾蘭數(shù)學(xué)家威廉?漢密爾頓爵士(SirWillianHamilton)于1859首先提出的。

定義9.5.2在圖G(有向圖或無向圖)中，如果存在一條路，經(jīng)過每個結(jié)點一次且僅一次，則該路稱為漢密爾頓路。如果存在一條回路，經(jīng)過每個結(jié)點一次且僅一次，則稱該路為漢密爾頓回路。具有漢密爾頓回路的圖稱為漢密爾頓圖。

與歐拉圖不同，判斷一個圖是否為漢密爾頓圖至今還沒有一個簡單的充分必要條件，只有一些必要條件和充分條件。判斷一個圖是漢密爾頓圖的充分必要條件是圖論中尚未解決的基本難題之一。下面介紹一些關(guān)于漢密爾頓圖的必要條件和充分條件。

先給出一個約定：設(shè)G=V,E是圖，SV，用G-S表示從圖G中刪除S中的所有結(jié)點所得的子圖。

定理9.5.4設(shè)無向圖G=V,E是漢密爾頓圖，S是V的任意非空子集，則W(G-S)≤|S|。證明：設(shè)C是G的一條漢密爾頓回路，v1S，則C-v1(從C中刪除結(jié)點v1)是一條路或回路，路上各結(jié)點相互連通。再刪除S中的另一個結(jié)點v2，則W(C-v1,v2)≤2，所以W(C-v1,v2)≤|v1,v2|。由歸納法可得W(C-S)≤|S|。又因為C-S是G-S的生成子圖，因而W(G–S)≤W(C–S)，所以有W(G–S)≤|S|。本定理的條件是漢密爾頓圖的必要條件，而不是充分條件。利用該定理可以證明一個圖不是漢密爾頓圖，即滿足此定理條件的圖不一定是漢密爾頓圖，而不滿足此定理條件的圖一定不是漢密爾頓圖。例如，圖9.34叫彼得松圖。彼得松圖滿足定理9.5.4的條件，但可以驗證它不是漢密爾頓圖。又如，在圖9.35中，令S=a,b，則W(G-S)=3，|S|=2，故W(G–S)≤|S|不成立。所以該圖不是漢密爾頓圖。【例9.5】設(shè)G是無向連通圖，證明：如果G中有割點或橋，則G一定不是漢密爾頓圖。證明：設(shè)v是割點。刪除結(jié)點v，圖成為不連通的，且至少有兩個連通分支。令S=v，則W(G–S)≥2＞1=|S|，即W(G–S)＞|S|。依據(jù)定理9.5.4，G不是漢密爾頓圖。如果G中有橋，則該橋的一個端點是割點?？梢詺w結(jié)為G中有割點的情況。所以G也不是漢密爾頓圖。

定理9.5.5設(shè)G=V,E是n階無向簡單圖，如果G中每一對結(jié)點度數(shù)的和大于等于n–1，則在G中存在一條漢密爾頓路。

推論

設(shè)G=V,E是n階無向簡單圖，如果G中每一對結(jié)點度數(shù)的和大于等于n，則在G中存在一條漢密爾頓回路。

定理9.5.5及其推論給出了圖中存在一條漢密爾頓路和漢密爾頓回路的充分條件，而不是必要條件。例如，圖9.37(a)有6個結(jié)點，任意兩個結(jié)點度數(shù)的和小于5，但圖中存在一條漢密爾頓路。又如圖圖9.37(b)也有6個結(jié)點，任意兩個結(jié)點度數(shù)的和小于6，但圖中存在一條漢密爾頓回路。

【例9.6】設(shè)G=V,E是一個無向簡單圖，|V|=n，|E|=m，設(shè)m＞(n–1)(n–2)。試證明G中存在一條漢密爾頓路。證明：先證明圖G中任意兩個不同的結(jié)點度數(shù)之和大于等于n-1，然后利用定理9.5.5即得本例要證的結(jié)果。用反證法，設(shè)圖G中存在兩個結(jié)點v1和v2，使得deg(v1)＋deg(v2)＜n–1，即deg(v1)＋deg(v2)≤n–2。刪去結(jié)點v1和v2后，得到圖G′，G′是具有n-2個結(jié)點的無向簡單圖。設(shè)G′的邊數(shù)為m′,則m′≥m-(n-2)＞(n-1)(n-2)-(n-2)=(n-2)(n-3)，即m′＞(n–2)(n–3)另一方面，G′是具有n–2個結(jié)點的無向簡單圖，它最多有(n–2)(n–3)條邊。所以m′≤(n–2)(n–3)。由此得出矛盾。所以deg(v1)＋deg(v2)≥n–1，由定理9.5.5得G中存在一條漢密爾頓路。

【例9.7】某地有5個風(fēng)景點，若每個風(fēng)景點均有兩條道路與其它點相通，問是否可經(jīng)過每個風(fēng)景點恰好一次的游完這5處?解：因為有5個風(fēng)景點，故可看成一個有5個結(jié)點的無向圖，其中每處均有兩條路與其它結(jié)點相通，所以deg(vi)=2，i=1,…,5。故對任意兩點vi，vj均有deg(vi)+deg(vj)=2+2=4=5-1由定理9.5.5可知此圖中一定有一條漢密爾頓路，本題有解。定義9.5.3給定圖G=V,E有n個結(jié)點，若將圖G中度數(shù)之和至少是n的非鄰接結(jié)點連接起來得圖G′，對圖G′重復(fù)上述步驟，直到不再有這樣的結(jié)點對存在為止，所得到的圖稱為原圖G的閉包，記作C(G)。例如圖9.38給出了有六個結(jié)點的圖G構(gòu)造其閉包的過程。在這個例子中C(G)是完全圖。一般情況下，C(G)也可能不是完全圖。

定理9.5.6設(shè)G是簡單圖,G是漢密爾頓圖當(dāng)且僅當(dāng)G的閉包是漢密爾頓圖。證明略。

下面通過一個例子，介紹一個判別漢密爾頓路不存在的方法?！纠?.8】圖G如圖9.39所示，證明G中沒有漢密爾頓路。

證明：任取一結(jié)點a用A標(biāo)記，所有與它相鄰接的結(jié)點標(biāo)記為B。繼續(xù)不斷地用A標(biāo)記所有鄰接于B的結(jié)點，再用B標(biāo)記所有鄰接于A的結(jié)點，直到所有的結(jié)點標(biāo)記完畢。如果圖中有一條漢密爾頓路，那么它必交替通過標(biāo)記A的結(jié)點和標(biāo)記B的結(jié)點，故或者標(biāo)記A的結(jié)點與標(biāo)記B的結(jié)點數(shù)一樣，或者兩者相差為1。然而本例有3個結(jié)點標(biāo)記A，5個結(jié)點標(biāo)記B，它們相差為2，所以該圖不存在漢密爾頓路。返回章目錄

9.6樹

樹是比較簡單而又特別重要的圖，它在計算機科學(xué)和技術(shù)中有非常廣泛的應(yīng)用。

9.6.1無向樹定義9.6.1連通無回路的無向圖稱為無向樹，簡稱樹。常用T表示。在樹中，度數(shù)為1的結(jié)點稱為樹葉，度數(shù)大于1的結(jié)點稱為分支點或內(nèi)點。規(guī)定，平凡圖也是樹，叫平凡樹。定義9.6.2

若無向圖至少有兩個連通分支，每一個連通分支是樹，則此無向圖稱為森林。無向樹有很多性質(zhì)，有些性質(zhì)是樹的充分必要條件，可以看作樹的等價定義。下面的定理是樹的6個充分必要條件，每一個都可以作為樹的定義使用。定理9.6.1設(shè)G=V,E是無向圖，|V|=n，|E|=m，則下列各命題是等價的：①G是樹。②G中每一對結(jié)點之間存在惟一的路。③G中無回路且m=n–1④G是連通的且m=n–1⑤G是連通的且G中任何邊均為橋。⑥

G中無回路，但在任何兩個不同的結(jié)點之間增加一個新邊，得到一個惟一的含新邊的回路。證明：①②

G是樹，所以G是連通的，uV，vV，u和v之間存在一條路。若路不惟一，設(shè)L1和L2都是u和v之間的路，則L1和L2組成了G中的一個回路，與G是樹矛盾。

②③先證G中無回路。若G中存在某個結(jié)點v上的自回路，uV，由條件知u到v存在一條路L1：u…v，因為v上有自回路，所以u到v存在另一條路L2：u…vv，這與G中每一對結(jié)點之間存在惟一的路矛盾。若G中存在長度大于等于2的一條回路，則回路上兩個結(jié)點之間存在不同的路。這與條件是矛盾的。所以G中無回路。以下用歸納法證明m=n–1。當(dāng)n=1時，G為平凡圖，m=0=1–1=n–1。結(jié)論成立。設(shè)n≤k時，結(jié)論成立。下證n=k+1時，結(jié)論也成立。設(shè)e=(u,v)是G中的一條邊，由于G中無回路，所以G-e(在G刪除邊e所得的子圖)有兩個連通分支G1和G2，設(shè)它們的結(jié)點數(shù)和邊數(shù)分別為：m1，n1和m2，n2。于是有n1≤k和n2≤k，由歸納假設(shè)知：m1=n1–1和m2=n2-1，m=m1＋m2＋1=n1-1＋n2-1＋1=n-1。③④只須證明G是連通的。若不然，設(shè)G有t(t≥2)個連通分支G1，G2，…，Gt，Gi中均無回路，都是樹。由①②③可知，mi=ni–1，i=1,…,t。于是m=m1＋m2＋…＋mt=n1-1＋n2-1＋…＋nt-1=n1＋n2＋…＋nt-t=n–t，由于t≥2，這與m=n–1矛盾。所以G是連通圖。

④⑤只須證明G的每一條邊均為橋。設(shè)e是G的任意邊，刪除e得子圖G1，G1中的邊數(shù)m1=m-1，G1中的結(jié)點數(shù)n1=n，m1=m–1=n-1-1=n-2=n1-2＜n1-1，由習(xí)題9.3的第3題知G1不是連通圖，所以e是橋。⑤⑥由于G中每一條邊均為橋，因而G中無回路。又因為G連通，所以G是樹。由①②知，uV，vV，u≠v，u與v之間存在一條惟一的路。在u與v之間增加一條新邊，就得到G的一條回路，顯然這條回路是惟一的。⑥①只須證明G是連通的，uV，vV，u≠v，在u與v之間增加一條新邊(u,v)就產(chǎn)生G的一個惟一的回路，故結(jié)點u和結(jié)點v連通。由于u與v是任意的，所以G是連通圖。定理9.6.2在任何n階非平凡的無向樹T中至少有兩片樹葉。證明：設(shè)樹T有x片樹葉，由定理9.1.1知，樹T中所有結(jié)點的度數(shù)之和等于邊數(shù)的2倍。依據(jù)定理9.6.1，在樹T中邊數(shù)等于結(jié)點數(shù)減1，即n–1。所以2(n–1)=。另一方面，樹中的分支點為n-x個，每個分支點的度數(shù)大于等于2，所有分支點度數(shù)之和大于等于2(n–x)，從而下式成立：2(n-1)=≥x+2(n-x)解之，得x≥2。9.6.2生成樹定義9.6.3

設(shè)G為無向圖，若G的生成子圖是一棵樹，則該樹稱為G的生成樹。設(shè)G的生成樹為T，則T中的邊稱為樹枝。G的不在生成樹T中的邊稱為弦。所有弦的集合稱為生成樹T的補。在圖9.40中，(b)是(a)的生成樹，e2,e3,e5,e6是樹枝，e1,e4是弦,e1,e4是該生成樹的補；(c)是(a)的生成樹，e1,e2,e3,e6是樹枝，e4,e5是弦，e4,e5是該生成樹的補。

定理9.6.3

無向圖G具有生成樹的充分必要條件是G為連通圖。證明：若無向圖G具有生成樹，顯然G為連通圖。以下證明若無向圖G為連通圖，則G具有生成樹。若連通圖G無回路，則G本身就是一棵生成樹；若G至少有一個回路，刪除此回路的一邊，得到子圖G1，它仍然連通，并與G有相同結(jié)點集。若G1無回路，則G1就是一棵生成樹；若G1仍有一個回路，再刪除G1回路上的一邊。重復(fù)上述過程，直至得到一個無回路的連通圖，該圖就是一棵生成樹。由定理9.6.3的證明過程可以看出，一個連通圖可以有多個生成樹。因為在取定一個回路后，就可以從中去掉任一條邊，去掉的邊不同，可能得到的生成樹也不同。

例如，在圖9.40(a)中相繼刪去邊e1和e4，就得到了生成樹(b)。相繼刪去邊e4和e5，就得到了生成樹(c)。推論1

無向連通圖G有n個結(jié)點和m條邊，則m≥n–1證明：由定理9.6.3的證明知，G有生成樹，設(shè)為T。|E(G)|=m，其中，E(G)是圖G的邊構(gòu)成的集合。依據(jù)定理9.6.1，|E(T)|=n–1,其中，E(T)是樹T的邊構(gòu)成的集合。而|E(G)|≥|E(T)|，所以m≥n–1。推論2在無向連通圖中，一個回路和任何一棵生成樹的補至少有一條公共邊。證明：若有一個回路和一棵生成樹的補無公共邊，那么，這個回路包含在該生成樹中，這與樹的定義矛盾。

推論3在無向連通圖中，一個邊割集和任何一棵生成樹至少有一條公共邊。證明：若有一個邊割集和一棵生成樹無公共邊，那么，刪除這個邊割集所得的子圖必包含該生成樹，從而該子圖是連通的。這與邊割集的定義矛盾。

設(shè)G為無向連通圖，有n個結(jié)點和m條邊。T為G的生成樹，T有n個結(jié)點和n-1條邊。所以要得到G的一棵生成樹，必須刪除G的m-(n-1)=m–n＋1條邊。定義9.6.4設(shè)G為無向連通圖，有n個結(jié)點和m條邊。要得到一棵生成樹，必須刪除G的m–n＋1條邊。m–n＋1稱為無向連通圖G的秩。無向連通圖的秩，與生成樹的選擇無關(guān)。

定義9.6.5

設(shè)G=V,E為無向連通圖，eE，對邊e指定一個正數(shù)C(e)，稱正數(shù)C(e)為邊e的權(quán)。設(shè)T是G的生成樹，T的所有邊e的權(quán)之和稱為樹T的權(quán)。記為C(T)。若G的每一條邊都指定權(quán)，則稱G為賦權(quán)圖。在實際應(yīng)用中，邊的權(quán)可以是長度，運輸量或其它費用。

定義9.6.6

在圖G的所有生成樹中，權(quán)最小的生成樹，稱為最小生成樹。定理9.6.4

設(shè)G=V,E為無向連通賦權(quán)圖，|E|=m，以下算法可以產(chǎn)生最小生成樹T：先將圖的m條邊按它的權(quán)由小到大的順序排列為：e1,e2,…,em。①取e1到T中。②在尚未檢查過的邊中從左到右依次檢查，若ej與T中的邊不能構(gòu)成回路，則取ej到T中，否則跳過。③反復(fù)做②，直到所有邊都已檢查。

定理9.6.4描述的算法叫克魯斯克爾(kruskal)算法?！纠?.8】圖9.41(a)給出了一個賦權(quán)圖G，用kruskal算法求出G的最小生成樹。解：先將m條邊按權(quán)由小到大排列：