圖論及其應(yīng)用

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

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

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

邊集，?邊數(shù)

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

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

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

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

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

習(xí)題

???1.1.1若G為簡(jiǎn)單圖，則????。

?2?abcrpqdef

G=(V,E)1.1.2n(?4)個(gè)人中，若每4人中一定有一人認(rèn)識(shí)其他3人，則一定有一人認(rèn)識(shí)其他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)之間各存在一一對(duì)應(yīng)關(guān)系，且這二對(duì)應(yīng)關(guān)系保持關(guān)聯(lián)關(guān)系。記為G?F。

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

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

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

1

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

空?qǐng)D（emptyg.）?E=?。

V?(?V)為獨(dú)立集?V?中任二頂點(diǎn)都互不相鄰。

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

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

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

例。用標(biāo)號(hào)法判定二部圖。習(xí)題

二部圖

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

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

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

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

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

(b).對(duì)簡(jiǎn)單二部圖有???2/4.

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

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

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

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

k-1

們恰有一個(gè)坐標(biāo)不同。證明k-方體有個(gè)頂點(diǎn)，k*2條邊，且是一偶圖。

1.2.8簡(jiǎn)單圖G的補(bǔ)圖Gc是指和G有一致頂點(diǎn)集V的一個(gè)簡(jiǎn)單圖，在Gc中兩個(gè)頂點(diǎn)相鄰當(dāng)且僅當(dāng)它們?cè)贕不相鄰。

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

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

2

*

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

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

A(G)=[ai,j]???,其中mi,j=頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)=0,1,2.ai,j=連接頂點(diǎn)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ǔ)簡(jiǎn)單圖（underlyingsimpleg.）。

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

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

以上兩種子圖，其實(shí)，對(duì)應(yīng)于取子圖的兩種基本運(yùn)算。下面是取子圖的另兩種基本運(yùn)算：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?雖有一致的邊集，但兩者不一定相等：后者一定是生成子圖，而前者則不然。

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

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

習(xí)題

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

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

c

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

頂點(diǎn)的度

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

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

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

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的度序列。證明：非負(fù)

4

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

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

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

*

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

路和連通性

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

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

yfv長(zhǎng)?邊數(shù)（重復(fù)計(jì)算）。

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

dhbW-1

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

圖)。例如，yvwx。

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

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

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

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

V1,,V?

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

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

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

記號(hào)對(duì)任一非

S?V，令S=V\