圖論課件第1章資料

yzwang@第一章圖的基本概念圖和簡單圖子圖與圖的運算路與圖的連通性最短路及其算法圖的代數(shù)表示及其特征極圖1.1圖和簡單圖

一、圖的定義定義

一個圖G定義為一個有序?qū)?V,E)，記為G=(V,E)，其中

(1)V是一個非空集合，稱為頂點集或點集，其元素稱為頂點或點；(2)E是由V中的點組成的無序點對構(gòu)成的集合，稱為邊集，其元素稱為邊，且同一點對在E中可出現(xiàn)多次。注：圖G的頂點集記為V(G)，邊集記為E(G)。圖G的頂點數(shù)(或階數(shù))和邊數(shù)可分別用符號n(G)和m(G)表示。例

設(shè)V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，則G=(V,E)是一個4階圖。若用小圓點代表點，連線代表邊，則可將一個圖用“圖形”來表示,如例中的圖可表示為v1v2v3v4注：也可記邊uv為e，即e=uv。v1v2v3v4e1e2e3e4e5例

設(shè)V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5}，其中

e1=v1v2，e2=v2v3，e3=v2v3，e4=v3v4，e5=v4v4，則G=(V,E)是一個圖。(1)

若邊e=uv,此時稱u和v是e的端點;并稱u和v相鄰，u(或v)與e相關(guān)聯(lián)。若兩條邊有一個共同的端點，則稱這兩條邊相鄰。(2)

孤立點：不與任何邊相關(guān)聯(lián)的點；自環(huán)：兩端點重合的邊；

重邊：連接兩個相同頂點的邊的條數(shù)，叫做邊的重數(shù)。重數(shù)大于1的邊稱為重邊。相關(guān)概念(4)

既沒有環(huán)也沒有重邊的圖稱為簡單圖。其他所有的圖都稱為復(fù)合圖。簡單圖非簡單圖例

平凡圖●(3)

點集與邊集均為有限集合的圖稱為有限圖，本書只討論有限圖。只有一個頂點而無邊的圖稱為平凡圖。邊集為空的圖稱為空圖。二、圖的同構(gòu)定義

設(shè)有兩個圖G1

=(V1,E1)和G2

=(V2,E2)，若在其頂點集合之間存在雙射，即存在一一對應(yīng)的關(guān)系，使得邊之間有如下的關(guān)系：設(shè)u1,v1∈V1

,u2,v2∈V2,

u1

?

u2,v1

?

v2,u1v1∈E1當且僅當u2v2∈E2，且u1v1的重數(shù)與u2v2相等，則稱兩圖同構(gòu)，記為G1≌G2。例≌注：(1)

兩個同構(gòu)的圖均有相同的結(jié)構(gòu)，沒有本質(zhì)上的差異,差異只是頂點和邊的名稱不同。(2)

圖同構(gòu)的幾個必要條件：①頂點數(shù)相同；②邊數(shù)相同；③度數(shù)相等的頂點個數(shù)相同。(3)

在圖的圖形表示中我們可以不給圖的點和邊標上符號，稱這樣的圖為非標定（號）圖，否則稱為標定（號）圖。非標定圖實際上是代表一類相互同構(gòu)的圖。不誤解時我們也不嚴格區(qū)分標定圖與非標定圖。

(4)判定圖的同構(gòu)是很困難的。對于規(guī)模不大的兩個圖，判定其是否同構(gòu)，可以采用觀察加推證的方法。定義設(shè)v為G的頂點，G中以v為端點的邊的條數(shù)(環(huán)計算兩次)稱為點v的度數(shù)，簡稱為點v的度，記為dG(v)，簡記為d(v)。d(v1)=5d(v2)=4d(v3)=3d(v4)=0d(v5)=2v1v2v3v4v5例

注：該圖中各點的度數(shù)之和等于14，恰好是邊數(shù)7的兩倍。例證明下面兩圖同構(gòu)。證明

作映射

f:vi?ui

(i=1,2….,10)，易知該映射為雙射。容易驗證，對

vivj

E((a))，有f(vivj)uiuj

E((b))，(1

i

10,1

j

10)由圖的同構(gòu)定義知，圖(a)與(b)是同構(gòu)的。v5v1v2v4v3v10v6v7v8v9(a)u1u2u3u4u5u6u7u8u9u10(b)例

判斷下面兩圖是否同構(gòu)。u1v1解兩圖不同構(gòu)。若兩圖同構(gòu)，則兩圖中唯一的與環(huán)關(guān)聯(lián)的兩個點u1與v1一定相對應(yīng)，而u1的兩個鄰接點與v1的兩個鄰接點狀況不同，u1鄰接有4度點，而v1沒有。所以，兩圖不同構(gòu)。例

指出4個頂點的非同構(gòu)的所有簡單圖。分析：四個頂點的簡單圖最少邊數(shù)為0，最多邊數(shù)為6，所以可按邊數(shù)進行枚舉。解(a)(b)(c)(d)(e)(f)(g)三、完全圖，偶圖，補圖定義任意兩點均相鄰的簡單圖稱為完全圖，在同構(gòu)意義下，n階完全圖只有一個，記為Kn。K2K3K4例

K2,K3,K4分別為如下圖所示。K30定義若一個圖的點集可以分解為兩個（非空）子集X和Y，使得每條邊的一個端點在X中，另一個端點在Y中，則這樣的圖稱為具有二分類（X,Y）的偶圖（或二部圖）。完全偶圖是指具有二分類(X,Y)的簡單偶圖，其中X的每個頂點與Y的每個頂點相連，若|X|=m，|Y|=n，則這樣的偶圖記為Km,n。例偶圖不是偶圖例

K3,3

K1,3

G1

G2

四個圖均為偶圖K1,3,K3,3為完全偶圖

偶圖是一種常見數(shù)學(xué)模型。例

學(xué)校有6位教師將開設(shè)6門課程。六位教師的代號分別是xi(i=1,2,3,4,5,6)，六門課程代號是yi

(i=1,2,3,4,5,6)。已知教師x1能夠勝任課程y2和y3；教師x2能夠勝任課程y4和y5；教師x3能夠勝任課程y2；教師x4能夠勝任課程y6和y3；教師x5能夠勝任課程y1和y6；教師x6能夠勝任課程y5和y6。請畫出老師和課程之間的狀態(tài)圖。解x1x5x4x3x2x6y4y3y1y2y5y6簡單圖G的補圖：設(shè)G=(V,E)，則圖H=(V,E1\E)稱為G的補圖，記為，其中集合例

下圖中的(a)，(b)兩圖是互補的。(a)(b)定理

若n階圖G是自補的（即），則

n=0,1(mod4)。證明因為G是自補的，則G和其補圖有同樣多的邊數(shù)，且邊數(shù)從而又因G的邊數(shù)m(G)是整數(shù)，故n(n-1)/4為整數(shù)，即只能有n≡0(mod4)

或(n-1)≡0(mod4)。

四、頂點的度、度序列設(shè)v為G的頂點，G中以v為端點的邊的條數(shù)(環(huán)計算兩次)稱為點v的度數(shù)，簡稱為點v的度，記為dG(v)，簡記為d(v)。奇點：度數(shù)為奇數(shù)的頂點相關(guān)術(shù)語和記號圖G的頂點的最小度圖G的頂點的最大度偶點：度數(shù)為偶數(shù)的頂點k-正則圖:每個點的度均為k的簡單圖例如，完全圖和完全偶圖Kn,n

均是正則圖。

對任意的有m條邊的圖G=(V,E)，有證明因圖G的任一條邊均有兩個端點(可以相同)，在計算度時恰被計算兩次(每個端點各被計算了一次)，所以各點的度數(shù)之和恰好為邊數(shù)的兩倍。定理

(圖論基本定理)注：該定理也稱為握手定理，是由歐拉提出的：在一個聚會上，朋友相互見面時握一次手，則握手次數(shù)是握手人次的兩倍。歐拉一生發(fā)表論文850余篇，著作25余部。推論

任意圖中，奇點的個數(shù)為偶數(shù)。證明設(shè)V1，V2分別是G中偶點集和奇點集。則由握手定理知：顯然第一個求和式為偶數(shù)，而第二個求和式中的每一項均為奇數(shù)，所以第二個求和式必然有偶數(shù)項，即度數(shù)為奇數(shù)的頂點個數(shù)必為偶數(shù)。推論

正則圖的階數(shù)和度數(shù)不同時為奇數(shù)。證明

設(shè)G是k-正則圖，若k為奇數(shù)，則由推論知正則圖G的點數(shù)必為偶數(shù)。

例

設(shè)Δ與δ是簡單圖G的最大度與最小度，求證：

證明由握手定理知所以定義一個圖G的各個點的度d1,d2,…,dn構(gòu)成的非負整數(shù)組(d1,d2,…,dn)稱為G的度序列。定理非負整數(shù)組(d1,d2,….,dn)是圖的度序列的充分必要條件是：∑di為偶數(shù)。證明必要性由握手定理立即得到。如果∑di為偶數(shù)，則數(shù)組中為奇數(shù)的數(shù)字個數(shù)必為偶數(shù)。按照如下方式作圖G:

若di為偶數(shù)，則在與之對應(yīng)的點作di/2個環(huán)；對于剩下的偶數(shù)個奇數(shù)，兩兩配對后分別在每配對點間先連一條邊，然后在每個頂點畫(dj-1)/2個環(huán)。該圖的度序列就是已知數(shù)組。定義對于一個非負整數(shù)組(d1,d2,…,dn)，若存在一個簡單圖G，以它為度序列，則稱這個數(shù)組是可圖的。可圖的序列簡稱為可圖序列或圖序列。關(guān)于可圖序列，主要研究3個問題：(1)

存在問題：什么樣的整數(shù)組是可圖序列？(2)計數(shù)問題：一個可圖序列對應(yīng)多少不同構(gòu)的圖？(3)構(gòu)造問題：如何畫出可圖序列對應(yīng)的所有不同構(gòu)圖？(1)徹底解決了；(2)解決得不好；(3)沒有解決。研究現(xiàn)狀定理設(shè)有非負整數(shù)組Π=(d1,d2,…,dn)滿足則Π是可圖序列的充分必要條件是：是可圖序列。證明充分性顯然，我們只需證明必要性。設(shè)G是Π對應(yīng)的簡單圖，d(vi)=di。情形1：點v1與點v2,v3,…,vd1+1鄰接，則刪去頂點v1及其關(guān)聯(lián)的邊所得到的圖的度序列正好為Π1。情形2：點v1與點vd1+2,…,vn的某些頂點鄰接。假設(shè)：設(shè)v1與vj0鄰接，但當k>j0時，v1與vk不鄰接；又設(shè)v1與vi0不鄰接，但當k<i0時，v1與點vk鄰接。v1v2v3vi0-1vj0vi0vn可以證明：在圖中必然存在一點u，使得u與vi0相鄰，但是它與vj0不相鄰！v1v2v3vi0-1vj0vi0vnu若不然，對任意的與vi0鄰接的點，若都與vj0鄰接，那么有dj0≥di0+1,這與條件矛盾！此時在圖中去掉邊v1vj0和vi0u，加上邊vj0u和v1vi0。顯然新圖與原圖度序列相同，但j0減小了，i0增大了！v1v2v3vi0-1vj0vi0vnu如此不斷進行下去，最后可以將情形2變?yōu)榍樾?。例

試判斷下列非負整數(shù)組Π是否可圖?解

根據(jù)定理可得下列非負整數(shù)組v3

v4

v5v1

v6v2

v7顯然Π3是可圖序列，因此是可圖的。五、圖的頻序列定理一個簡單圖G的n個點的度不能互不相同。

證明因為圖G

為簡單圖，所以△(G)≤n-1。

情形1：若G

沒有孤立點，則因為頂點個數(shù)為n，所以必有兩個頂點度數(shù)相同。情形2：若G僅有一個孤立點，設(shè)G1表示G去掉孤立點后的部分，則同理，在G1里必有兩頂點度數(shù)相同。情形3：若G有兩個以上的孤立點，則定理顯然成立。定義設(shè)n階圖G的各點的度取s個不同的非負整數(shù)d1,d2,…,ds。又設(shè)度為di的點有bi個(∑bi=n)，則稱(b1,b2,…,bs)為G的頻序列。

定理一個n階圖G和它的補圖有相同的頻序列。證明由補圖的定義知，點v在圖G及其補圖中的度數(shù)之和為n-1，即因此，若G中有bi個度為di的點，則這bi個點在G的補圖中的度變?yōu)閚-1-di

。故G與其補圖有相同的頻序列。1.2

子圖與圖的運算一、子圖定義

設(shè)G和H為兩個圖，若V(H)

V(G)，E(H)

E(G)，且H中邊的重數(shù)不超過G中對應(yīng)邊的重數(shù)，則稱H是G的子圖。記為H

G。有時又稱G是H的母圖。

當H

G，但H

≠

G時，則記為H

G，且稱H為G的真子圖。G的生成子圖是指滿足V(H)=V(G)的子圖H。簡單地說，圖G的任意一部分(包括G自身和空圖)都稱為是圖G的的一個子圖。在上圖中，H1與H2均為G的子圖，其中H2是G的生成子圖，而H1則不是。v1v2v3v4v5v1v3v4v2G

H1

v1v3v4v2v5

H2例例求G的所有生成子圖。123G解定理具有m條邊的簡單標號圖的生成子圖的個數(shù)為2m。定義

設(shè)V’是V的一個非空子集。以V’為頂點集，以兩端點均在V’中的邊的全體為邊集所組成的子圖，稱為G的由V’導(dǎo)出的子圖，記為G[V’]；簡稱為G的導(dǎo)出子圖。導(dǎo)出子圖G[V\V’]記為G-V’：它是G中刪除V’中的頂點以及與這些頂點相關(guān)聯(lián)的邊所得到的子圖。若V’={v}，則把G-{v}簡記為G–v。例

求G[V’]，其中V’={1,3,5}。12345G解135G[V’]定義

假設(shè)E’是E的非空子集。以E’為邊集，以E’中邊的端點全體為頂點集所組成的子圖稱為G的由E’導(dǎo)出的子圖，記為G[E’]，簡稱為G的邊導(dǎo)出子圖。G–E’表示從圖G中刪去E’中的邊之后的子圖。例求G[E’]，其中E’={13,24,35}。12345G12345G[E’]若E’={e}，則用G–e來代替G–{e}。解二、圖的運算G1和G2不相交：指它們無公共頂點。G1和G2邊不重：指它們無公共邊。并圖G1∪G2：是指其頂點集為V(G1)∪V(G2)，邊集為E(G1)∪E(G2)的G的一個子圖；如果G1和G2是不相交的,就記其并圖為G1+G2。

交圖G1∩G2

：類似地定義，但二者至少要有一個公共頂點。對稱差G1△G2

：G1△G2=(G1∪G2)-(G1∩G2)=(G1-G2)∪(G2-G1)。設(shè)G1，G2是G

的子圖，有下列術(shù)語與概念：差圖G1-G2

：在G1中去掉G2中的邊組成的圖。例則1324abcdefG12354G2dcehijgG1∩G234dce2G1∪G24132abcdef5hijg例則1324abcdefG12354G2dcehijgG1－G2fab31244235G2－G1ghjiG1△G2fab31245ihgj定義

在不相交的G1和G2的并圖G1+G2中，把G1的每個頂點和G2的每個頂點連接起來所得到的圖稱為G1和G2的聯(lián)圖，記為G1∨G2。例K1∨K4=K5，K2∨K3=K5

K6=K1∨K5=K2∨K4=K3∨K3。v1

v2v4

v3

G2u1G1v1

v2v4

v3

G1∨G2u1不難看出：定義

設(shè)G1=(V1,E1)，G2=(V2,E2)，對點集V=V1×V2中的任意兩個點u=(u1,u2)和v=(v1,v2)，當(u1=v1和u2adjv2)或(u2=v2和u1adjv1)時就把u和v連接起來所得到的圖G稱為G1和G2的積圖，記為G=G1×G2。其中uiadjvi表示ui和vi鄰接。u1v1

G1u2v2w2

G2(u1,u2)(u1,v2)(u1,w2)(v1,u2)(v1,v2)(v1,w2)

G1×G2例定義

設(shè)G1=(V1,E1)，G2=(V2,E2)，對點集V=V1×V2中的任意兩個點u=(u1,u2)和v=(v1,v2)，當(u1adjv1)或(u1=v1和u2adjv2)時就把u和v連接起來所得到的圖G稱為G1和G2的合成圖，記為G=G1[G2]。例

已知G1與G2，求G1[G2]和G2[G1]。G1124G235解G2[G1](3,1)(3,2)(4,1)(4,2)(5,1)(5,2)(1,4)(1,3)(1,5)(2,3)(2,4)(2,5)G1[G2]若G1的點數(shù)和邊數(shù)為n1,m1，G2的點數(shù)和邊數(shù)為n2,m2，經(jīng)過聯(lián)、積、合成三種運算，圖的點數(shù)和邊數(shù)為n1n2G2[G1]n1n2G1[G2]n1m2+n2m1n1n2G1×G2m1+m2+n1n2n1+n2G1∨G2邊數(shù)點數(shù)運算圖的積運算是網(wǎng)絡(luò)構(gòu)造的常用方法。并行計算機中的網(wǎng)絡(luò)拓撲常采用所謂的“超立方體”結(jié)構(gòu)。采用該結(jié)構(gòu)可使網(wǎng)絡(luò)具有較好的可靠性、較小的通信延遲和很好的可擴展性以及便于并行編程等優(yōu)點。超立方體Qn，簡稱n方體，可以采用積圖來遞歸構(gòu)造：

(1)1方體：Q1=K2。

(2)

n方體定義為：Qn=K2×Qn-1。Q1Q2Q3超立方體常采用下面簡單的遞歸構(gòu)造方法：n方體Qn的頂點可用一個長度為n的二進制碼來表示。Qn的頂點數(shù)目正好等于2n個。由n-1方體Qn-1構(gòu)造Qn的方法是：(1)

將Qn-1拷貝復(fù)制一次；(2)

將原Qn-1每個頂點的二進制碼前再添加一個零，將復(fù)制得來的n-1方體每個頂點的二進制碼前面再添加一個1;(3)

在這兩個n-1方體之間連線：當且僅當兩個頂點二進制碼只有一位對應(yīng)位數(shù)字不同時，該兩點連線。01110010

Q2=K2×K2例101111100110001000011010Q3=K2×K2×K2關(guān)于n方體Qn的性質(zhì)研究，可以查閱到很多文獻。Y.SaadandM.H.Schultz,TopologicalPropertiesofHypercubes,IEEETrans.Comput.,37(1988),867--872.經(jīng)典文章是：定義把G1的任意一個頂點和G2的任意一個頂點等同起來得到的新圖稱為G1與G2的聯(lián)合，記為G1●G2。例H1=K2●K2H2=K3●K2對圖的路與連通性進行研究，在計算機網(wǎng)絡(luò)研究中有著十分重要的意義。因為網(wǎng)絡(luò)的抽象就是一個圖。研究網(wǎng)絡(luò)信息傳遞，信息尋徑是主要問題之一，這恰對應(yīng)于圖中路的研究；在網(wǎng)絡(luò)研究中，可靠性也是主要問題之一，它與圖的連通性問題相對應(yīng)。1.3

路和連通性一、途徑、跡、路、圈、距離和直徑定義給定圖G=(V,E)，w=v0e1v1e2…ekvk是G中點邊交替組成的序列，其中vi∈V，ei∈E，若w滿足ei的端點為vi-1與vi，則稱w為一條從頂點v0到頂點vk的途徑（或通道或通路)，簡稱(v0,vk)途徑。頂點v0和vk分別稱為w的起點和終點，其他點稱為內(nèi)部點，途徑中的邊數(shù)稱為它的長度。定義邊不重復(fù)的途徑稱為跡；點不重復(fù)的跡稱為路。定義起點和終點相同的途徑、跡和路分別稱為閉途徑、閉跡和圈。閉途徑也稱為環(huán)游，閉跡也稱為回路。長度為k的圈稱為k圈，k為奇數(shù)時稱為奇圈，k為偶數(shù)時稱為偶圈。3圈常稱為三角形。自環(huán)是長度為1的圈。易知，若圖中兩個不同點u與v間存在途徑，則u與v間必存在路；若過點u存在閉跡，則過點u必存在圈。定義聯(lián)結(jié)u和v的長度最短的路的長度，稱為u與v的距離，記為d(u,v)。在簡單圖中，途徑可以簡單地由其頂點序列來表示。定義圖G的直徑定義為d(G)=max{d(u,v)|u,v∈V}。例在圖G中，取w1=v1v2v3，w2=v1v2v3v4v2，w3=v1v2v3v2v3v4，

v1v4v5v3v2G則w1,w2,w3依次為長為2,4,5的途徑；其中w1與w2為跡，w1為路；直徑d(G)=2。另外由定義可看出，v1v2v5v1為長為3的圈，v1v2v3v4v2v5v1為長為6的回路。二、圖的連通性定義圖G中點u與v稱為是連通的，如果u與v間存在通路。否則稱u與v不連通。定義如果圖G中任意兩點是連通的，稱G是連通圖，否則稱G是非連通圖。非連通圖中每一個極大連通部分，稱為G的連通分支。G的連通分支的個數(shù)，稱為G的分支數(shù)，記為ω(G)。連通圖非連通圖

G

D●ω(G)=1ω(D)=3例例證明：在n(n≥2)階連通圖中(1)至少有n-1條邊；(2)如果邊數(shù)大于n-1，則至少有一個圈；(3)如果恰有n-1條邊，則至少有一個1度頂點。證明

(1)

若G中沒有1度頂點，由握手定理：若G中有1度頂點u，對G的頂點數(shù)作數(shù)學(xué)歸納。當n=2時，結(jié)論顯然；設(shè)結(jié)論對n=k時成立。當n=k+1時，考慮G-u，它仍然為連通圖，所以G-u至少含有k-1條邊。于是G的邊數(shù)≥k。(2)

對于非簡單圖，結(jié)論顯然成立。故假設(shè)G是簡單圖。若W是路，則長為n-1；但由于G的邊數(shù)大于n-1，因此，存在兩點vi與vj，它們相異，但鄰接。于是為G的一個圈。由于G連通，則G中必存在一條途徑：若W不是路，則存在一個頂點u在W中多次出現(xiàn)，因此聯(lián)結(jié)u的第一次出現(xiàn)與第二次出現(xiàn)的途徑可化簡為一個圈。(3)

若不然，G中頂點度數(shù)至少為2，于是由握手定理知：

這與G中恰有n-1條邊矛盾！例證明：若δ≥2，則G中必然含有圈。

證明只就連通的簡單圖證明即可！設(shè)該點為vm，則vmvm+1….vkvm為G中的一個圈。設(shè)W=v1v2…vk-1vk是G中的一條最長路。由于δ≥2，所以vk必然有相異于vk-1的相鄰頂點。又因為W是G中最長路，所以這樣的點必然是v1,v2,…,vk-2中之一。例

設(shè)G是具有m條邊的n階簡單圖，證明：若G的直徑為2且Δ=n-2，則m≥2n-4。證明

設(shè)d(v)=Δ=n-2，且設(shè)v的鄰接點為v1,v2,…,vn-2，

u是剩下的一個頂點。由于d(G)=2且u不能和v相鄰，所以u至少和v1,v2…,vn-2中的一個頂點鄰接，否則有d(G)>2。(非連通圖的直徑定義為∞)不妨假設(shè)u和v1,v2,…,vk相鄰。為了保證u到各點距離不超過2，vk+1,….vn-2這些頂點的每一個必須和前面v1,v2,…,vk中某點相鄰，這樣，圖中至少又有n-2條邊。因此，總共至少有2n-4條邊。定理

若圖G是不連通的，則其補圖是連通圖。證明因G是不連通，故G中至少兩個分支。設(shè)u，v是G的任意兩個頂點。若u和v在G中不鄰接，則在補圖中它們鄰接。若u和v在G中鄰接，則它們屬于G的同一分支。在另一個分支中取一點w，則在補圖中u和v均與w鄰接，從而uwv是一條途徑,故在補圖中它們鄰接。因此G的補圖是連通圖。定理設(shè)圖G為n階圖，若G中任意兩個不相鄰頂點u與v滿足d(u)+d(v)≥n-1，則G是連通圖且d(G)≤2。證明我們將證明，對G中任意兩點x與y，一定存在一條長度至多為2的連接x與y的路。若x和y相鄰，則上述論斷成立。若x和y不相鄰，則一定存在一點w與x和y均相鄰。若不然，在G的剩下的n-2個頂點中，假設(shè)有k個與x鄰接，但與y不鄰接，有l(wèi)個頂點和y鄰接，但不與x鄰接，同時假定有m個頂點與x和y均不相鄰。那么d(x)=k，d(y)=l。由于k+l+m=n-2，所以d(x)+d(y)=n-2-m≤n-2，矛盾！三、偶圖判定定理定理

一個圖是偶圖當且當它不包含奇圈。證明一個圖是偶圖當且僅當每個連通分支是偶圖，一個圈只能屬于一個連通分支，因此我們只需對連通圖證明即可。設(shè)G是具有二分類(X,Y)的偶圖，并且C=v0v1…vkv0是G的任意一個圈。不失一般性，可假定v0∈X。這樣，v2i∈X，且v2i

+1∈Y。又因為v0∈X，所以vk∈Y。由此即得C是偶圈。接下來證明充分性。設(shè)G是不包含奇圈的連通圖。任選一個頂點u且定義V的一個分類（X,Y）如下：X={x|d

(u,x)是偶數(shù)，x∈V(G)}，Y={y

|d

(u,y)是奇數(shù)，y∈V(G)}?，F(xiàn)在證明(X,Y)是G的一個二分類。斷言：對X中任意兩點v與w，必不相鄰！設(shè)P是一條最短(u,v)路，而Q是一條最短的(u,w)路。設(shè)u1是P和Q的最后一個交點。由于P，Q是最短路，所以P，Q中u到u1段長度相同，因此奇偶性相同。又因為P，Q的長度均是偶數(shù)，所以P，Q中u1v段和u1w段奇偶性相同。如果v與w相鄰，則可得到奇圈，矛盾！所以(X,Y)是G的一個二分類。類似地，Y中任意兩個頂點也不相鄰。QPvuwu11.4最短路及其算法定義若圖G的每一條邊e都附有一個實數(shù)w(e)，稱為e的權(quán),則G連同它邊上的權(quán)稱為賦權(quán)圖。若H是一個賦權(quán)圖，則H的各邊權(quán)之和稱為圖H的權(quán)，記為W(H)。例

右圖G為賦權(quán)圖，v1v3v2v4

G

1

3

5

6

5其中w(v1v2)=1，w(v1v3)=5，W(G)=20。一、

賦權(quán)圖

定義設(shè)G為賦權(quán)圖，u與v是G中兩點，在連接u與v的所有路中，各邊權(quán)值之和最小的路，稱為u與v間的最短路，最短路的長度稱為u與v的距離，仍記為d(u,v)。例求v2與v4的距離。v1v3v2v4

G

1

31

6

3易知，各邊的權(quán)均為1的賦權(quán)圖中的路長與非賦權(quán)圖中的路長是一致的。解d(v2,v4)=5。相應(yīng)的最短路為Γ：v2v1v3v4。二、最短路問題

許多最優(yōu)化問題都可轉(zhuǎn)化為在一個賦權(quán)圖中找出某類具有最?。ɑ蜃畲螅?quán)的子圖，其中之一就是最短路問題：給出一個連接各城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)之間試確定一條最短路線。數(shù)學(xué)模型：在一個賦權(quán)圖中的兩個指定頂點a和b之間找出一條最短(a,b)路。1959年，Dijkstra發(fā)表了一篇名為“ANoteonTwoProblemsinConnexionwithGraphs

”，這篇僅有兩頁半的文章發(fā)表在一流期刊《Numerischemathematik》上面。這篇文章給出了解決最短路問題的著名的Dijkstra算法，同時指出：在此之前Ford和Berge已經(jīng)分別給出了解決最短路問題的方法。巧合的是，同年11月，“線性規(guī)劃之父”Dantzig提交了一篇名為“OntheShortestPathRouteThroughaNetwork”的論文，該論文第二年正式發(fā)表在Top期刊《ManagementScience》上面。該論文只有三頁半，也提出了解決最短路問題的算法，同時也提到Ford的工作。2003年，Dantzig在其著作《LinearProgramming》中曾提到“Aboutthesametime,Dijkstra

independentlyproposedarefinedversionofthesamealgorithmforfindingtheshortestdirectedpathsfromanodetoallothernodes.”，但Dantzig并未給出具有說服力的依據(jù)。但肯定的是，F(xiàn)ord在NetworkFlowTheory方面的工作是最短路問題的先驅(qū)，也是Dijkstra和Dantzig工作的基礎(chǔ)。Dantzig算法(頂點標號法)

t(ak)：點ak的標號值，表示點a1=a

到ak的最短路長度；Ai={a1,a2,...,ai}：已經(jīng)標號的頂點集合；Ti

：a1到ai的最短路上的邊所在的集合；

l(e)：邊e的權(quán)重；記號說明：Dantzig算法不僅找到了最短的(a,b)路，而且給出了a到圖G的所有其他頂點的最短路。

N(ak)：與點ak相鄰的所有點的集合，稱為ak的鄰集。Dantzig算法(1)記a1=a,t(a1)=0,A1={a1},T1=?;(2)若已經(jīng)得到Ai

={a1,a2,…,ai}，且對于1≤k≤i，已知t(ak)。對每一個ak∈Ai，求一點：使得：(3)設(shè)有mi

，1≤mi≤i，而bmi(i)是使取最小值。令：(4)若ai+1=b，停止；否則，記，

轉(zhuǎn)(2)。例

如圖所示，求點a到點b的距離。812614227924693av1v2v3v4v5v6b

1.A1={a}，t(a)=0，T1=?;2.b1(1)=v3;3.m1=1，a2=v3，t(v3)=t(a)+l(av3)=1(最小)，T2={av3};解14.A2={a,v3}，

b1(2)=v1，b2

(2)=v2；812614227924693av1v2v3v4v5v6b15.m2=1，a3=v1，t(v1)=t(a)+l(av1)=2(最小)，T3={av3,av1}；6.A3={a,v3,v1}，b1

(3)=v2，b2

(3)=v2，b3

(3)=v4；7.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小)，T4={av3,av1,v1v4}

8.A4={a,v3,v1,v4}，b1(4)=v2，b2(4)=v2，b3(4)=v2,b4(4)=v5；9.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小)，T5={av3,av1,

v1v4,v4v5};236236812614227924693av1v2v3v4v5v6b110.A5={a,v3,v1,v4,v5}，b1(5)=v2，b2(5)=v2，b3(5)=v2

,

b4(5)=v2,b5(5)=v2;11.m5=4,a6=v2,t(v2)=t(v4)+l(v4v2)=7(最小)，T6={av3,av1,v1v4,v4v5,v4v2};12.A6={a,v3,v1,v4,v5,v2},b2(6)=v6,b4(6)=b，b5(6)=v6，

b6(6)=v6;13.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小)，7914.A7={a,v3,v1,v4,v5,v2,v6},b4(7)=b，b5(7)=b，b7(7)=b;15.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小)，T8={av3,av1,v1v4,v4v5,v4v2,v2v6,v6b};于是知a與b的距離d(a,b)=t(b)=11，最短路為

T7={av3,av1,v1v4,v4v5,v4v2,v2v6};1179236812614227924693av1v2v3v4v5v6b11.5圖的代數(shù)表示及特征一、鄰接矩陣定義

設(shè)n階標定圖G=(V,E)，V={v1,v2,…,vn}，則G的鄰接矩陣是一個n×n矩陣A(G)=[aij](簡記為A)，其中若vi鄰接vj，則aij=1；否則aij=0。注：若aij取為連接vi與vj的邊的數(shù)目，則稱A為推廣的鄰接矩陣。用鄰接矩陣或關(guān)聯(lián)矩陣表示圖，稱為圖的代數(shù)表示。用矩陣表示圖，主要有兩個優(yōu)點：(1)能夠把圖輸入到計算機中；(2)可以用代數(shù)方法研究圖論。鄰接矩陣

推廣的鄰接矩陣

v1v2v4v3e1e2e3e4e5例(1)

鄰接矩陣是一個對稱方陣。

(2)

簡單標定圖的鄰接矩陣的各行(列)元素之和是該行(列)對應(yīng)的點的度。

(3)若A1和A2是對應(yīng)于同一個圖的兩種不同的標定的鄰接矩陣，則

A1和A2

是相似的，即存在一個可逆矩陣P使得A1=P-1A2P。(4)G是連通的當且僅當沒有G的點的一種標定法使它的鄰接矩陣有約化的形式鄰接矩陣的性質(zhì)v1到v1的長為2的通道的數(shù)目為1v1到v2的長為2的通道的數(shù)目為0v1到v3的長為2的通道的數(shù)目為2v1到v4的長為2的通道的數(shù)目為0

v2到v2的長為2的通道的數(shù)目為5

v1v2v4v3e1e2e3e4e5左圖的推廣的鄰接矩陣為例計算得圖中定理

令G是一個有推廣鄰接矩陣A的p階標定圖，則An的i行j列元素aij(n)等于由vi到vj的長度為n的通道的數(shù)目。證明當n=0時，A0=In(n階單位矩陣)，從任一點到自身有一條長度為零的通道，任何不同的兩點間沒有長度為零的通道，從而命題對n=0成立。由于aik是聯(lián)結(jié)vi和vk的長度為1的通道的數(shù)目，akj(n)是聯(lián)結(jié)vk和vj的長度為n的通道的數(shù)目，所以aikakj(n)表示由vi經(jīng)過vk到vj的長度為n+1的通道數(shù)目。假設(shè)命題對n成立，由An+1=AAn，故這表明命題對n+1成立。于是對所有的k求和便得到了由vi到vj的長度為n+1的通道數(shù)目，即aij(n+1)為由vi到vj的長度為n+1的通道數(shù)目。推論

設(shè)A為簡單圖G的鄰接矩陣，則(1)A2的元素aii(2)是vi的度數(shù)。A3的元素aii(3)是含vi的三角形的數(shù)目的兩倍。(2)若G是連通的，對于i≠j，vi與vj之間的距離是使An的aij(n)≠0的最小整數(shù)n。二、關(guān)聯(lián)矩陣定義

無環(huán)圖G的關(guān)聯(lián)矩陣B(G)=[bij](簡記為B)是一個n×m矩陣，當點vi與邊ej關(guān)聯(lián)時bij=1，否則bij=0。例B=e1

e2e3e4e5e6e7v1v2v3v4v5注：定義中“無環(huán)”的條件可去掉，此時bij=點vi與邊ej關(guān)聯(lián)的次數(shù)（0,1,2(環(huán))）。例e1v4v3v2v1e7e5e4e3e2e6e1e5v2

v5

e6e7

e2e4v1v3

e3

v4性質(zhì)關(guān)聯(lián)矩陣的每列和為2；其行和為對應(yīng)頂點的度數(shù)。三、鄰接譜定義圖的鄰接矩陣A(G)的特征多項式：稱為圖G的特征多項式。定義圖的鄰接矩陣A(G)的特征多項式的特征值及其重數(shù)，稱為圖G的鄰接譜，簡稱譜，記為Spec(G)。例求Kn的譜。解

Kn的鄰接矩陣為：計算得因此例若兩個非同構(gòu)的圖具有相同的譜，則稱它們是同譜圖。求證：右面兩圖是同譜圖。GH解

G與H顯然不同構(gòu)。通過直接計算得所以G與H是同譜圖。例設(shè)簡單圖G=(n,m)的譜為則證明因A的各特征值的平方組成矩陣A2的特征值，所以又因為A2的對角線元素的和為因此例設(shè)λ是簡單圖G=(n,m)的任意特征值，則：證明設(shè)λ=λ1,λ2,

…,λn是G的全部特征值。因為G是簡單圖，從而A(G)的對角元全為零，所以又因為對向量(1,1,…,1)與(λ2,λ3,λ4,…,λn)應(yīng)用柯西-施瓦茨不等式，得將上述兩式分別代入第一個式子的左端和右端，便可得證。注：對于圖譜的研究，開始于20世紀60年代。形成了代數(shù)圖論的主要研究方向之一。圖譜研究在流體力學(xué)，量子化學(xué)，量子物理與非線性物理以及網(wǎng)絡(luò)技術(shù)中都有重要的應(yīng)用。四、圖的鄰接代數(shù)定義設(shè)A是無環(huán)圖G的鄰接矩陣，容易驗證對于矩陣的加法和數(shù)與矩陣的乘法來說構(gòu)成復(fù)數(shù)域C上的向量空間，稱該空間為圖G的鄰接代數(shù)。定理

設(shè)G為n階無環(huán)連通圖，則d(G)＋1≤dimΛ(G)≤n。證明由矩陣理論知，鄰接代數(shù)的維數(shù)等于鄰接矩陣的最小多項式的次數(shù)。所以最小多項式的次數(shù)不超過n，因此dimΛ(G)≤n。下面證明I,A,A2,…,Ad(G)

線性無關(guān)。若不然，則存在不全為零的數(shù)a0,a1,…,ad(G)使得設(shè)al-1≠0，但當l≤

k

≤

d(G)

時，有ak=0，從而由哈密爾頓－凱萊定理知顯然，d(G)<n。于是，d(v1,vk

)=k-1，(k=1,2,…,d(G)+1)。注意到：Ak的元素a1l(k)在k<l-1時為零，而a1l

(l-1)>0。第1行第l列的元素為al-1a1l(l-1)≠0。所以矩陣因此產(chǎn)生矛盾！假定v1v2…vd(G)+1是G中一條最短的(v1,vd(G)+1)路。定理設(shè)G

為n階連通無環(huán)圖，則A(G)的不同特征值的個數(shù)s滿足不等式證明

s≤n

顯然成立。由矩陣理論知：非負對稱矩陣的不同特征值的個數(shù)等于其最小多項式的次數(shù)，而最小多項式的次數(shù)等于G的鄰接代數(shù)的維數(shù)，所以：注：具有n個點的路的直徑顯然為n-1，因此n點路的鄰接代數(shù)的維數(shù)為n。注：n點路的不同特征值的個數(shù)為n。完全圖Kn的直徑顯然為1，不同特征值的個數(shù)恰好為2。五、圖空間具有m條邊的簡單圖的生成子圖的個數(shù)顯然為2m。設(shè)G1,G2,…,GN（N=2m）表示簡單圖G的全部生成子圖。定理集合M={G1,G2,…,GN}在對稱差運算△與數(shù)乘運算0●Gi=?

，1●Gi=Gi下，構(gòu)成數(shù)域F={0,1}上的一個m維向量空間。注：圖空間是網(wǎng)絡(luò)圖論中的一個基本概念。學(xué)習(xí)網(wǎng)絡(luò)圖論的主要基礎(chǔ)是電工學(xué)與矩陣理論知識。研究通信網(wǎng)絡(luò)，如果涉及圖論方法，建議參看陳樹柏，《網(wǎng)絡(luò)圖論及其應(yīng)用》，科學(xué)出版社，1982年。1.6極圖

P.Erdos是該研究領(lǐng)域的杰出人物，也是數(shù)學(xué)界的傳奇人物，國際圖論大師，獲過Wolf數(shù)學(xué)獎。他是20世紀最偉大的數(shù)學(xué)家之一，也是人類歷史上發(fā)表數(shù)學(xué)論文最多的數(shù)學(xué)家(1525篇)，第二名是歐拉(850余篇)，第三名是柯西(789篇)。他于1996年9月20日因心臟病去世，享年83歲，他的逝世當時驚動了整個數(shù)學(xué)界。

極圖屬于極值圖論的范疇，主要研究滿足某個條件下的最大圖或最小圖問題。

20世紀70年代末，極值圖論已經(jīng)形成了相對完整的理論體系，但還有很多引人入勝的公開性問題沒有解決，所以，直到現(xiàn)在，它仍然是重要研究方向。但是，該方向是比較困難的數(shù)學(xué)研究方向之一。一、l部圖的概念與特征定義

若簡單圖G的點集V有一個劃分：且所有的Vi非空，Vi

內(nèi)的點均不鄰接，稱G是一個l部圖。4部圖例注：(1)

如果l=2，則G就是偶圖;(2)

任何一個n階圖必是一個n部圖;(3)

若l1<l2≤n，任意的l1部圖也是

l2部圖。定義

如果在一個l部圖G中,|Vi|=ni,任何兩點u∈Vi,v∈Vj,

i≠j,i,j=1,2,…,l均鄰接，則稱G為完全l部圖。記作例注；完全l部圖也可表示為。邊數(shù)：點數(shù)：

v1v2v3

v4

v6v5K1,2,3定義

如果在一個n個點的完全l部圖G中，n=kl+r(0≤r<l)|V1|=|V2|=…=|Vr|=k+1,|Vr+1|=|Vr+2|=…=|Vl|=k則稱G為n階完全l幾乎等部圖，記為Tl,n。|V1|=|V2|=…=|Vl

|的完全l幾乎等部圖