圖論及其應(yīng)用

本文格式為Word版，下載可任意編輯——圖論及其應(yīng)用圖和子圖圖

圖G=(V,E)，其中V={

}V頂點集，?頂點數(shù)

邊集，?邊數(shù)

E={e1,e2,,e?}例。左圖中，V={a,b,,f},E={p,q,ae,af,,ce,cf}注意，左圖僅僅是圖G的幾何實現(xiàn)（代表），它們有無窮多個。真正的圖G是上面所給出式子，它與頂點的位置、邊的形狀等無關(guān)。不過今后對兩者將經(jīng)常不加以區(qū)別。

稱邊ad與頂點a(及d)相關(guān)聯(lián)。也稱頂點b(及f)與邊bf相關(guān)聯(lián)。

稱頂點a與e相鄰。稱有公共端點的一些邊彼此相鄰，例如p與af。

環(huán)（loop，selfloop）：如邊l。棱（link）：如邊ae。重邊：如邊p及邊q。簡單圖：（simplegraph）無環(huán)，無重邊平凡圖：僅有一個頂點的圖（可有多條環(huán)）。一條邊的端點：它的兩個頂點。

?(G)?E(G).。記號：?(G)?V(G),

習(xí)題

???1.1.1若G為簡單圖，則????。

?2?abcrpqdef

G=(V,E)1.1.2n(?4)個人中，若每4人中一定有一人認識其他3人，則一定有一人認識其他n-1人。

同構(gòu)

在下圖中，圖G恒等于圖H,記為G=H?VG)=V(H),E(G)=E(H)。圖G同構(gòu)于圖F?V(G)與V(F),E(G)與E(F)之間各存在一一對應(yīng)關(guān)系，且這二對應(yīng)關(guān)系保持關(guān)聯(lián)關(guān)系。記為G?F。

注往往將同構(gòu)慨念引伸到非標號圖中，以表達兩個圖在結(jié)構(gòu)上是否一致。

xadwcxdwca?x?d?w?c?babb?yezyezy?e?z?G=(V,E)

H=(V?,E?)F=(V??,E??)

1

注判定兩個圖是否同構(gòu)是NP-hard問題。完全圖(completegraph)Kn

空圖（emptyg.）?E=?。

V?(?V)為獨立集?V?中任二頂點都互不相鄰。

二部圖（偶圖，bipartiteg.）G=(X,Y;E)?存V(G)的一個2-劃分(X,Y),使X與Y都是獨立集。

完全二部圖Km,n?二部圖G=(X,Y)，其中X和Y之間的每對頂點都相鄰，且?X?=m,?Y?=n。

K1K2K3K4K5類似地可定義，完全三部圖（例如Km,n,p），完全n-部圖等。

例。用標號法判定二部圖。習(xí)題

二部圖

1.2.1G?H??(G)=?(H),?(G)=?(H)。并證明其逆命題不成立。1..2.2證明下面兩個圖不同構(gòu)：

1.2.3證明下面兩個圖是同構(gòu)的：

1.2.4證明兩個簡單圖G和H同構(gòu)?存在一一映射f:V(G)?V(H)，使得uv?E(G)當且僅當

f(u)f(v)?E(H)。

1.2.5證明：(a).?(Km,n)=mn;

(b).對簡單二部圖有???2/4.

1.2.6記Tm,n為這樣的一個完全m-部圖：其頂點數(shù)為n，每個部分的頂點數(shù)為[n/m]或{n/m}個。證明：

?n?k??k?1?(a).?(Tm,n)=???(m?1)??其中k=[n/m].

?2??2?K3,3K1,5K2,2,2(b).對任意的n頂點完全m-部圖G，一定有?(G)??(Tm,n)，且僅當G?Tm,n時等式才成立。

1.2.7所謂k-方體是這樣的圖：其頂點是由0與1組成的有序k-元組，其二頂點相鄰當且僅當它

k-1

們恰有一個坐標不同。證明k-方體有個頂點，k*2條邊，且是一偶圖。

1.2.8簡單圖G的補圖Gc是指和G有一致頂點集V的一個簡單圖，在Gc中兩個頂點相鄰當且僅當它們在G不相鄰。

(a).畫出Kcn和Kcm,n。

(b).假使G?Gc則稱簡單圖G為自補的。證明：若G是自補的，則??0,1(mod4)

2

*

關(guān)聯(lián)矩陣M(G)與鄰接矩陣A(G)

M(G)=[mi,j]???,

A(G)=[ai,j]???,其中mi,j=頂點vi與邊ej的關(guān)聯(lián)次數(shù)=0,1,2.ai,j=連接頂點vi與vj的邊數(shù)。

例。

e1??M(G)?????1100e21100e30110e40011e51001e60002e71?v1?0v2?1?v3?0?v4v1e1e2e5e6v4e4G=(V,E)v3e7e3v2

v1??A(G)?????0211v22023v31101v41011?v1?v?2?v3??v4

子圖

子圖(subgraph)H?G?V(H)?V(G),E(H)?E(G)。真子圖H?G。母圖（supergraph）。

生成子圖（spanningsubg.）?H?G且V(H)=V(G)。生成母圖。

基礎(chǔ)簡單圖（underlyingsimpleg.）。

導(dǎo)出子圖（inducedsubg.）G[V?],(非空V??V)?以V?為頂點集，以G中兩端都在V?上的邊全體為邊集構(gòu)成的G的子圖。邊導(dǎo)出子圖G[E?]非空E??E?以E?為邊集，以E?中所有邊的端點為頂點集的的子圖。例。

ueydxcfghwG[{u,w,x,y}]G[{u,w,x}]avbG[{f,c]}G[{c,d,e}]

以上兩種子圖，其實，對應(yīng)于取子圖的兩種基本運算。下面是取子圖的另兩種基本運算：G-V’?去掉V?及與V?相關(guān)聯(lián)的一切邊所得的剩余子圖。

G=(V,E)

3

?即G[V\\V?]

G-E’?從中去掉E?后所得的生成子圖

例。G-{b,d,g},(=G[E\\{b,d,g}])G-{b,c,d,g},(?G[E\\{b,c,d,g}])G-{a,e,f,g}.(?G[E\\{a,e,f,g}])

注意G[E\\E?]與G-E?雖有一致的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。

上述四種運算是最基本取子圖運算，今后老要遇到，一定要認真把握好。關(guān)于子圖的一些定義還有：G+E??往G上加新邊集E?所得的（G的母）圖。為簡單計，今后將G?{e}簡計為G?e；G-{v}簡計為G-v。設(shè)G1,G2?G，稱G1與G2為不相交的（disjiont）?V(G1)?V(G2)=?(?E(G1)?E(G2)=?)

邊不相交（edge-distjiont）?E(G1)?E(G2)=?。(但這時G1與G2仍可能為相交的）。并圖G1?G2,當不相交時可簡記為G1+G2.交圖G1?G2.

習(xí)題

1.4.1證明：完全圖的每個導(dǎo)出子圖是完全圖；偶圖的每個導(dǎo)出子圖是偶圖。

1.4.2設(shè)G為一完全圖，1?n??-1。證明：若??4，且G中每個n頂點的導(dǎo)出子圖均有一致

c

的邊數(shù)，則G?K?或K?。

頂點的度

頂點v的度dG(v)=G中與頂點v相關(guān)聯(lián)邊數(shù)。（每一環(huán)記為2）最大、最小度?，?。（?(G),?(G))定理1.1(handshakinglemma)任一圖中，?d(v)?2?.

v?V系1.1任一圖中，度為奇數(shù)頂點的個數(shù)為偶數(shù)。

例。任一多面體中，邊數(shù)為奇數(shù)的外表面的數(shù)目為偶數(shù)。證明。作一圖，使其頂點對應(yīng)于多面體的面，并使其中二頂點相鄰當且僅當對應(yīng)的兩個面相鄰。?

k-正則圖（k-regularg.)?d(v)=k,?v?V.習(xí)題

0-正則圖1-正則圖2-正則圖3-正則圖1.5.1證明：??2?/???。

1.5.2若k-正則偶圖(k>0)的2-劃分為(X,Y),則

?X?=?Y?。

1.5.3在人數(shù)>1的人群中，總有二人在該人群中有一致的朋友數(shù)。

1.5.4設(shè)V(G)={v1,v2,,v?}，則稱(d(v1),d(v2),,d(v?))為G的度序列。證明：非負

4

n整數(shù)序列(d1,d2,,dn)為某一圖的度序列?

?di?1i是偶數(shù)。

1.5.5證明：任一無環(huán)圖G都包含一偶生成子圖H，使得dH(v)?dG(v)/2對所有v?V成立。

*

1.5.6設(shè)平面上有n個點，其中任二點間的距離?1，證明：最多有3n對點的距離=1。

路和連通性

途徑（walk)例如（u，x）-途徑W=ueyfvgyhwbvgydxdydx(有限非空序列）=uyvywvyxyx(簡寫法當不引起混淆時）起點（origin）u。終點（terminus）x。u內(nèi)部頂點（internalvertex）y,v,w,x。

ea（注意，中間出現(xiàn)的x也叫內(nèi)部頂點。）

yfv長?邊數(shù)（重復(fù)計算）。

g節(jié)（段，section）。例如W的(y,w)-節(jié)=yvw。

dhbW-1

（逆途徑）,WW’（兩條途徑W與W?相銜接）。跡(trail)?邊各不一致的途徑。例如，yvwyx。xcw路(path)?頂點各不一致的途徑。（可當作一個圖或子

圖)。例如，yvwx。

d(u,v)=u與v之間最短路的長。例。（命題）G中存在(u,v)-途徑?G中存在(u,v)-路。

G中頂點u與v為連通的(connected)?G中存在(u,v)-路

(?G中存在(u,v)-途徑。)

V上的連通性是V上的等價關(guān)系，它將V劃分為（等圖G價類）：

V1,,V?

使每個Vi中的任二頂點u及v都連通（即存在(u,v)-路）。稱每個G[Vi]i=1,2,?

為G的一個分支（component）;稱?(G）為G的分支數(shù)。G為連通圖??(G)=1

?G中任兩點間都有一條路相連。G為非連通圖??(G)?1。

記號對任一非

S?V，令S=V\