圖論課件第1章資料

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

一、圖的定義定義

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

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

設(shè)V={v1,v2,v3,v4}，E={v1v2,v1v2,v2v3}，則G=(V,E)是一個4階圖。若用小圓點(diǎn)代表點(diǎn)，連線代表邊，則可將一個圖用“圖形”來表示,如例中的圖可表示為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的端點(diǎn);并稱u和v相鄰，u(或v)與e相關(guān)聯(lián)。若兩條邊有一個共同的端點(diǎn)，則稱這兩條邊相鄰。(2)

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

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

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

平凡圖●(3)

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

設(shè)有兩個圖G1

=(V1,E1)和G2

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

,u2,v2∈V2,

u1

?

u2,v1

?

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

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

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

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

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

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

作映射

f:vi?ui

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

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)的兩個點(diǎn)u1與v1一定相對應(yīng)，而u1的兩個鄰接點(diǎn)與v1的兩個鄰接點(diǎn)狀況不同，u1鄰接有4度點(diǎn)，而v1沒有。所以，兩圖不同構(gòu)。例

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

K2,K3,K4分別為如下圖所示。K30定義若一個圖的點(diǎn)集可以分解為兩個（非空）子集X和Y，使得每條邊的一個端點(diǎn)在X中，另一個端點(diǎn)在Y中，則這樣的圖稱為具有二分類（X,Y）的偶圖（或二部圖）。完全偶圖是指具有二分類(X,Y)的簡單偶圖，其中X的每個頂點(diǎn)與Y的每個頂點(diǎn)相連，若|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的補(bǔ)圖：設(shè)G=(V,E)，則圖H=(V,E1\E)稱為G的補(bǔ)圖，記為，其中集合例

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

若n階圖G是自補(bǔ)的（即），則

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

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

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

均是正則圖。

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

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

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

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

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

例

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

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

若di為偶數(shù)，則在與之對應(yīng)的點(diǎn)作di/2個環(huán)；對于剩下的偶數(shù)個奇數(shù)，兩兩配對后分別在每配對點(diǎn)間先連一條邊，然后在每個頂點(diǎn)畫(dj-1)/2個環(huán)。該圖的度序列就是已知數(shù)組。定義對于一個非負(fù)整數(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è)有非負(fù)整數(shù)組Π=(d1,d2,…,dn)滿足則Π是可圖序列的充分必要條件是：是可圖序列。證明充分性顯然，我們只需證明必要性。設(shè)G是Π對應(yīng)的簡單圖，d(vi)=di。情形1：點(diǎn)v1與點(diǎn)v2,v3,…,vd1+1鄰接，則刪去頂點(diǎn)v1及其關(guān)聯(lián)的邊所得到的圖的度序列正好為Π1。情形2：點(diǎn)v1與點(diǎn)vd1+2,…,vn的某些頂點(diǎn)鄰接。假設(shè)：設(shè)v1與vj0鄰接，但當(dāng)k>j0時，v1與vk不鄰接；又設(shè)v1與vi0不鄰接，但當(dāng)k<i0時，v1與點(diǎn)vk鄰接。v1v2v3vi0-1vj0vi0vn可以證明：在圖中必然存在一點(diǎn)u，使得u與vi0相鄰，但是它與vj0不相鄰！v1v2v3vi0-1vj0vi0vnu若不然，對任意的與vi0鄰接的點(diǎn)，若都與vj0鄰接，那么有dj0≥di0+1,這與條件矛盾！此時在圖中去掉邊v1vj0和vi0u，加上邊vj0u和v1vi0。顯然新圖與原圖度序列相同，但j0減小了，i0增大了！v1v2v3vi0-1vj0vi0vnu如此不斷進(jìn)行下去，最后可以將情形2變?yōu)榍樾?。例

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

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

v4

v5v1

v6v2

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

證明因?yàn)閳DG

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

情形1：若G

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

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

。故G與其補(bǔ)圖有相同的頻序列。1.2

子圖與圖的運(yùn)算一、子圖定義

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

V(G)，E(H)

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

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

當(dāng)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條邊的簡單標(biāo)號圖的生成子圖的個數(shù)為2m。定義

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

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

假設(shè)E’是E的非空子集。以E’為邊集，以E’中邊的端點(diǎn)全體為頂點(diǎn)集所組成的子圖稱為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}。解二、圖的運(yùn)算G1和G2不相交：指它們無公共頂點(diǎn)。G1和G2邊不重：指它們無公共邊。并圖G1∪G2：是指其頂點(diǎn)集為V(G1)∪V(G2)，邊集為E(G1)∪E(G2)的G的一個子圖；如果G1和G2是不相交的,就記其并圖為G1+G2。

交圖G1∩G2

：類似地定義，但二者至少要有一個公共頂點(diǎn)。對稱差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的每個頂點(diǎn)和G2的每個頂點(diǎn)連接起來所得到的圖稱為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)，對點(diǎn)集V=V1×V2中的任意兩個點(diǎn)u=(u1,u2)和v=(v1,v2)，當(dāng)(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)，對點(diǎn)集V=V1×V2中的任意兩個點(diǎn)u=(u1,u2)和v=(v1,v2)，當(dāng)(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的點(diǎn)數(shù)和邊數(shù)為n1,m1，G2的點(diǎn)數(shù)和邊數(shù)為n2,m2，經(jīng)過聯(lián)、積、合成三種運(yùn)算，圖的點(diǎn)數(shù)和邊數(shù)為n1n2G2[G1]n1n2G1[G2]n1m2+n2m1n1n2G1×G2m1+m2+n1n2n1+n2G1∨G2邊數(shù)點(diǎn)數(shù)運(yùn)算圖的積運(yùn)算是網(wǎng)絡(luò)構(gòu)造的常用方法。并行計算機(jī)中的網(wǎng)絡(luò)拓?fù)涑２捎盟^的“超立方體”結(jié)構(gòu)。采用該結(jié)構(gòu)可使網(wǎng)絡(luò)具有較好的可靠性、較小的通信延遲和很好的可擴(kuò)展性以及便于并行編程等優(yōu)點(diǎn)。超立方體Qn，簡稱n方體，可以采用積圖來遞歸構(gòu)造：

(1)1方體：Q1=K2。

(2)

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

+1∈Y。又因?yàn)関0∈X，所以vk∈Y。由此即得C是偶圈。接下來證明充分性。設(shè)G是不包含奇圈的連通圖。任選一個頂點(diǎn)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中任意兩點(diǎn)v與w，必不相鄰！設(shè)P是一條最短(u,v)路，而Q是一條最短的(u,w)路。設(shè)u1是P和Q的最后一個交點(diǎn)。由于P，Q是最短路，所以P，Q中u到u1段長度相同，因此奇偶性相同。又因?yàn)镻，Q的長度均是偶數(shù)，所以P，Q中u1v段和u1w段奇偶性相同。如果v與w相鄰，則可得到奇圈，矛盾！所以(X,Y)是G的一個二分類。類似地，Y中任意兩個頂點(diǎn)也不相鄰。QPvuwu11.4最短路及其算法定義若圖G的每一條邊e都附有一個實(shí)數(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中兩點(diǎn)，在連接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)圖中的兩個指定頂點(diǎ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算法(頂點(diǎn)標(biāo)號法)

t(ak)：點(diǎn)ak的標(biāo)號值，表示點(diǎn)a1=a

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

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

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

N(ak)：與點(diǎn)ak相鄰的所有點(diǎn)的集合，稱為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，求一點(diǎn)：使得：(3)設(shè)有mi

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

轉(zhuǎn)(2)。例

如圖所示，求點(diǎn)a到點(diǎn)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階標(biāo)定圖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)點(diǎn)：(1)能夠把圖輸入到計算機(jī)中；(2)可以用代數(shù)方法研究圖論。鄰接矩陣

推廣的鄰接矩陣

v1v2v4v3e1e2e3e4e5例(1)

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

(2)

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

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

A1和A2

是相似的，即存在一個可逆矩陣P使得A1=P-1A2P。(4)G是連通的當(dāng)且僅當(dāng)沒有G的點(diǎn)的一種標(biāo)定法使它的鄰接矩陣有約化的形式鄰接矩陣的性質(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階標(biāo)定圖，則An的i行j列元素aij(n)等于由vi到vj的長度為n的通道的數(shù)目。證明當(dāng)n=0時，A0=In(n階單位矩陣)，從任一點(diǎn)到自身有一條長度為零的通道，任何不同的兩點(diǎ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矩陣，當(dāng)點(diǎn)vi與邊ej關(guān)聯(lián)時bij=1，否則bij=0。例B=e1

e2e3e4e5e6e7v1v2v3v4v5注：定義中“無環(huán)”的條件可去掉，此時bij=點(diǎn)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)頂點(diǎn)的度數(shù)。三、鄰接譜定義圖的鄰接矩陣A(G)的特征多項(xiàng)式：稱為圖G的特征多項(xiàng)式。定義圖的鄰接矩陣A(G)的特征多項(xiàng)式的特征值及其重數(shù)，稱為圖G的鄰接譜，簡稱譜，記為Spec(G)。例求Kn的譜。解

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

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

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

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

線性無關(guān)。若不然，則存在不全為零的數(shù)a0,a1,…,ad(G)使得設(shè)al-1≠0，但當(dāng)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

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

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

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

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

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

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

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

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

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

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

l2部圖。定義

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

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

v1v2v3

v4

v6v5K1,2,3定義

如果在一個n個點(diǎ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幾乎等部圖