周曉聰-zxc-g2basic基本概念

[有向圖]

設(shè)V是一個(gè)非空有限集，A是V上的二元關(guān)系。二元組G=(V,A)稱(chēng)為（有向）圖，V中元素稱(chēng)為頂點(diǎn)，A中元素稱(chēng)為?。ㄓ邢蜻叄?。關(guān)系A(chǔ)的關(guān)系圖就是圖G的圖解。[自環(huán)]

A中的自反性圖解為環(huán)形，稱(chēng)為自環(huán)。[多重邊]

在表達(dá)實(shí)際問(wèn)題的圖解中可能出現(xiàn)重復(fù)的關(guān)系定義，稱(chēng)為多重邊。2.1圖的概念[簡(jiǎn)單圖]不出現(xiàn)自環(huán)或多重邊圖解形狀的圖稱(chēng)為簡(jiǎn)單圖。未加特別聲明時(shí)，只討論簡(jiǎn)單圖。[完全圖]任何兩個(gè)頂點(diǎn)之間都有弧相連的圖稱(chēng)為完全圖。頂點(diǎn)集為V的完全圖GV=(V,VV)。[零圖]

A=或|A|=0時(shí)，稱(chēng)G為零圖。[平凡圖]

|V|=1時(shí)，稱(chēng)G為平凡圖。[圖的階]

|V|稱(chēng)為圖的階。2.1圖的概念[子圖]

G=(V,A)是G=(V,A)的一個(gè)子圖當(dāng)且僅當(dāng):⑴V

V⑵A

是V

上的二元關(guān)系⑶A

A上述定義中，若對(duì)u,vV，<u,v>A必有<u,v>A，則稱(chēng)G是G的一個(gè)極大子圖。G是G的子圖；若G

是G的子圖，則G

的任何子圖也是G的子圖；平凡圖是任何圖的子圖2.1圖的概念[生成子圖]

G=(V,A)是G=(V,A)的一個(gè)子圖且V=V，則稱(chēng)G

是G的一個(gè)生成子圖或支撐子圖。[導(dǎo)出子圖]

G=(V,A)，SV且S，則G中以S為頂點(diǎn)集的極大子圖稱(chēng)為G中由S導(dǎo)出的子圖。

[補(bǔ)圖]

設(shè)圖G=(V,A)，則~G=(V,VVA)稱(chēng)為G=(V,A)的補(bǔ)圖。

2.1圖的概念[無(wú)向圖]

圖G=(V,A)，當(dāng)A為對(duì)稱(chēng)關(guān)系時(shí)，在圖解上用線(xiàn)段替換成對(duì)出現(xiàn)的弧，在集合上用E={(u,v)|u

V,vV，<u,v>A，

<v,u>

A}

替換A，得到無(wú)向圖的形式，記為G=(V,E)。無(wú)向圖的各種概念完全類(lèi)似于有向圖的相關(guān)定義。n階無(wú)向完全圖記作Kn，其邊數(shù)=n(n1)/2。圖解中既有無(wú)向邊，又有有向邊的圖，稱(chēng)為混合圖?；旌蠄D可以化為有向圖求解。2.1圖的概念[定義]

對(duì)G=(V,A)，vi

V，分別定義其正關(guān)聯(lián)集、負(fù)關(guān)聯(lián)集、正鄰接集、負(fù)鄰接集如下：

Inc+(vi)={ak|(vj)(vjV

ak=<vi,vj>A)}

●以為vi起點(diǎn)的所有邊構(gòu)成的集合

Inc(vi)={ak|(vj)(vjV

ak=<vj,vi>A)}

●以為vi終點(diǎn)的所有邊構(gòu)成的集合

Adj+(vi)={vj|

vjV(ak)(ak=<vi,

vj>A)} Adj(vi)={vj|

vjV(ak)(ak=<vj,vi>A)}

●與vi相鄰的頂點(diǎn)構(gòu)成的集合2.2點(diǎn)和邊的關(guān)聯(lián)關(guān)系[關(guān)聯(lián)集與鄰接集]

對(duì)無(wú)向圖G=(V,E)，viV，分別定義其關(guān)聯(lián)集、鄰接集如下：

Inc(vi)={ek

|(vj)(vjV

ek=(vi,vj)E)}

Adj(vi)={vj|

vjV(ek)(ek=(vi,

vj)E)}[正負(fù)度]

對(duì)G=(V,A)，vi

V，分別定義其正度、負(fù)度、度如下：Deg+(vi)=|Inc+(vi)|Deg(vi)=|Inc(vi)|Deg(vi)=Deg+(vi)+Deg(vi)2.2點(diǎn)和邊的關(guān)聯(lián)關(guān)系[無(wú)向圖的度]

對(duì)G=(V,E)，vi

V，定義其度如下：

Deg(vi)=|Inc(vi)|

對(duì)簡(jiǎn)單圖顯然有：

Deg(vi)<|V|。[定理2-1]

對(duì)G=(V,E)，有：

對(duì)G=(V,A)有同樣的結(jié)論；[推論1]

圖中度為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。2.2點(diǎn)和邊的關(guān)聯(lián)關(guān)系[定義]

對(duì)無(wú)向圖G=(V,E)，若其任一頂點(diǎn)的度都為r，則稱(chēng)G為一個(gè)r度正則圖。[例]

n階完全圖是n1度正則圖。[推論2]

3度正則圖中有偶數(shù)個(gè)頂點(diǎn)。2.2點(diǎn)和邊的關(guān)聯(lián)關(guān)系圖解法具有不唯一性。例：一一對(duì)應(yīng)的兩個(gè)關(guān)系，具有相同的代數(shù)性質(zhì)，在一定意義上可視為同一。2.3同構(gòu)[同構(gòu)]

圖G=(V,A)和G=(V,A)，若存在一一對(duì)應(yīng)映射g:VV，使得對(duì)

v1,v2

V，v1,v2

A當(dāng)且僅當(dāng)

g(v1),g(v2)

A，則稱(chēng)G和G同構(gòu)。記為:GG[例]尋求判定圖同構(gòu)的一般方法是圖論的重要課題之一。2.3同構(gòu)[自補(bǔ)圖]

圖G=(V,A)，~G是G的補(bǔ)圖。若G~G，則稱(chēng)圖G是自補(bǔ)的（或自補(bǔ)圖）。[例]2.3同構(gòu)[有向道路]

有向圖G=(V,A)中，一條有向道路指的是一個(gè)點(diǎn)與弧的有限非空交替序列

=

v0

a1

v1

a2

v2

……

akvk

(k1)

其中viV(i=0..k),ajA(j=1..k)

且aj=<vj1,vj>(j=0..k)

v0

和vk分別稱(chēng)為的起點(diǎn)和終點(diǎn)，k稱(chēng)為的長(zhǎng)度。在簡(jiǎn)單圖中，也可記作=(v0v1v2……

vp

)或

v0

v1

v2

……

vp

2.4道路與回路[跡]若對(duì)任意的ij有ai

aj

，稱(chēng)之為簡(jiǎn)單有向道路/跡。[回路]若v0=vn

，稱(chēng)之為封閉的。簡(jiǎn)單封閉有向道路（閉跡）稱(chēng)為有向回路。[路]若對(duì)任意的ij有vi

vj

，稱(chēng)之為有向路（路徑）/初級(jí)道路/基本道路。[圈]若對(duì)任意的ij有vi

vj

而例外地v0=vn，稱(chēng)之為初級(jí)回路/圈。兩個(gè)頂點(diǎn)之間若有道路存在則必有路存在。無(wú)向圖具有完全類(lèi)似的定義。

2.4道路與回路[定理2-2]

無(wú)向圖G=(V,E)，u,v

V且uv。若u,v

之間存在兩條不同的路，則G中存在一條回路。[證明]

（構(gòu)造法）[定理2-3]

無(wú)向圖G=(V,E)中每個(gè)頂點(diǎn)的度均為偶數(shù)，且至少有一個(gè)頂點(diǎn)不是孤立點(diǎn)，則

G中存在一條回路。

[證明]

（反證法）設(shè)v不是孤立點(diǎn)，從v出發(fā)的最長(zhǎng)簡(jiǎn)單路徑經(jīng)過(guò)的頂點(diǎn)是v0(=v)v1…vn-1vn，則必存在0i<n使得vn=vi，否則與vn的度是偶數(shù)矛盾。2.4道路與回路[定理2-4]

G=(V,A)，|V|=n，則

G中任何初級(jí)道路的長(zhǎng)度均不大于n1；G中任何初級(jí)回路的長(zhǎng)度均不大于n

。

[證明](反證法)設(shè)圖中有一條道路，其長(zhǎng)度>n1，則其中至少有n+1個(gè)頂點(diǎn)標(biāo)號(hào)，而圖中只有n個(gè)頂點(diǎn)，故其中至少有兩個(gè)相同的頂點(diǎn)，即該道路不會(huì)是初級(jí)道路。2.4道路與回路[可達(dá)性]

G=(V,A)中，若從

vi

到vj

存在一條路，則稱(chēng)從

vi

到vj

是可達(dá)的，或稱(chēng)

vi

可達(dá)vj

。對(duì)無(wú)向圖G=(V,E)，結(jié)點(diǎn)間的可達(dá)性是對(duì)稱(chēng)的。若規(guī)定任何結(jié)點(diǎn)到其自身可達(dá)，則①可達(dá)性構(gòu)成V上的一個(gè)等價(jià)關(guān)系，其對(duì)V的每一個(gè)劃分塊可以構(gòu)成G的一個(gè)導(dǎo)出子圖。②兩個(gè)結(jié)點(diǎn)可達(dá)當(dāng)且僅當(dāng)它們屬于同一個(gè)導(dǎo)出子圖。③上述導(dǎo)出子圖的個(gè)數(shù)（或劃分塊個(gè)數(shù)）稱(chēng)為G的連通分支數(shù)，記為W(G)。2.4道路與回路[連通性]

G=(V,E)中，任意兩點(diǎn)之間可達(dá)時(shí)，稱(chēng)G為連通的（連通圖）。

G=(V,A)中，任意兩點(diǎn)之間相互可達(dá)時(shí)，稱(chēng)G為強(qiáng)連通的；若去掉弧的方向后得到的無(wú)向圖G=(V,s(A))是連通的，則稱(chēng)原來(lái)的G是弱連通的。G中的一個(gè)極大連通子圖稱(chēng)為G的一個(gè)連通分支。2.4道路與回路[定理2-5]

G=(V,E)，n=|V|，若對(duì)任意u,v

V且

uv，都有：Deg(u)+Deg(v)n1，則G連通。[證明](反證法)設(shè)G可分為不連通的兩部分G1=(V1,E1)和G2=(V2,E2)，選取

uV1,vV2

則Deg(u)<|V1|，Deg(v)<|V2|，故Deg(u)+Deg(v)<|V1|+|V2|=n，與Deg(u)+Deg(v)n1矛盾。注意：未加特別聲明時(shí)，我們討論的都是簡(jiǎn)單圖。2.4道路與回路[Euler回路]

若連通圖G=(V,E)中存在一條簡(jiǎn)單回路（無(wú)重復(fù)邊）經(jīng)過(guò)G的所有邊，則稱(chēng)該回路為G中的一條Euler回路。存在Euler回路的圖稱(chēng)為Euler圖。[定理2-6-1]

設(shè)有連通圖G=(V,E)，則下述命題等價(jià)：

(1)G是一個(gè)Euler圖；

(2)G的每一個(gè)頂點(diǎn)的度是偶數(shù)；[證明]（見(jiàn)戴一奇教材p16定理2.3.1）2.5Euler回路注意定理中對(duì)圖的連通性的假定；Euler回路經(jīng)過(guò)圖的所有邊一次且僅僅一次。定理對(duì)非簡(jiǎn)單圖也成立；定理的證明過(guò)程給出了為一個(gè)Euler圖構(gòu)造Euler回路的構(gòu)造算法。[定理2-7]

設(shè)連通圖G=(V,E)中恰有2k個(gè)頂點(diǎn)度為奇數(shù)，k1。則G的邊可劃分成k條簡(jiǎn)單道路。[證明]（構(gòu)造法，見(jiàn)戴一奇教材p17例2.3.3）2.5Euler回路[有向圖的Euler回路]

若有向連通圖G=(V,A)中存在一條簡(jiǎn)單有向回路經(jīng)過(guò)G的所有弧，則稱(chēng)該回路為G中的一條Euler回路，稱(chēng)該圖為Euler有向圖。[定理2-6-2]

設(shè)連通有向圖G=(V,A)，則下述命題等價(jià)：

(1)G是一個(gè)Euler有向圖；

(2)G的每一個(gè)頂點(diǎn)的入度等于出度；[證明]（略）2.5Euler回路[旋轉(zhuǎn)鼓的設(shè)計(jì)]

見(jiàn)戴一奇教材p17例2.3.42.5Euler回路[Hamilton路]

若連通圖G=(V,E)中存在一條初級(jí)道路（無(wú)重復(fù)頂點(diǎn)）經(jīng)過(guò)G中每個(gè)頂點(diǎn)一次，則稱(chēng)該道路為G中的一條Hamilton路。存在Hamilton回路的圖稱(chēng)為Hamilton圖。Hamilton路經(jīng)過(guò)圖的所有頂點(diǎn)一次且僅僅一次。引入記號(hào)：G=(V,E)，SV。從G中去除S中的頂點(diǎn)及其關(guān)聯(lián)邊得到的G的子圖記為GS。2.6Hamilton道路[定理2-8]

若G=(V,E)是一個(gè)Hamilton圖，SV且S，則G的子圖GS的連通分支數(shù)

W(GS)|S|[證明]

記G中H-回路為C，C中包含了G中所有頂點(diǎn)?？疾霤S：每從C中去除屬于S的一個(gè)頂點(diǎn)，連通分支數(shù)至多增加1（第一次以及當(dāng)該頂點(diǎn)處于邊緣時(shí)操作不會(huì)增加連通分支數(shù)），故

W(CS)|S|

而G可視為向C中添加邊構(gòu)成，故W(GS)W(CS)

所以W(GS)|S|2.6Hamilton道路定理給出了Hamilton圖的必要條件，可用于對(duì)Hamilton圖的否定性判定，但對(duì)Hamilton圖的肯定性判定無(wú)效。2.6Hamilton道路[例]

圖G12345786令S={2,6}，則W(GS)=3。而|S|=2，即W(GS)>|S|故圖G不可能是Hamilton圖。134578圖G-S2.6Hamilton道路[例]

Petersen圖。|V|=10，對(duì)任何SV，都有W(GS)S，但Petersen圖不是Hamilton圖。2.6Hamilton道路[定理2-9]

簡(jiǎn)單圖G=(V,E)，n=|V|，若對(duì)任一對(duì)不相鄰頂點(diǎn)u,vV,uv，有Deg(u)+Deg(v)n1，則G中存在一條Hamilton路。[證明]見(jiàn)戴一奇教材p18定理2.4.1[推論]

上述有Deg(u)+Deg(v)n時(shí)，G為Hamilton圖。[證明]見(jiàn)戴一奇教材p19推論2.4.12.6Hamilton道路定理及其推論給出了Hamilton圖成立的充分條件，可用于對(duì)Hamilton圖的肯定性判定。Hamilton圖成立的充要條件尚未得到解決，是圖論求解的課題之一。2.6Hamilton道路[鄰接矩陣]

對(duì)有向圖G=(V,R)，n=|V|，構(gòu)造矩陣A=(aij)nn，其中[定理2-10]

設(shè)A1、A2分別為G1、G2的鄰接矩陣，則G1G2當(dāng)且僅當(dāng)存在置換矩陣P，使得A1=PA2PT。

aij

=1<vi,vj>R0其他稱(chēng)A為圖G的鄰接矩陣。2.7圖的鄰接矩陣[定理2-11]

設(shè)Ann是G的鄰接矩陣，則連接vi與vj（ij）的長(zhǎng)度為l的路徑的條數(shù)等于A(yíng)l的第i行第j列的元素的數(shù)值。[證明]（數(shù)學(xué)歸納法：對(duì)l歸納）2.7圖的鄰接矩陣[道路矩陣]

對(duì)有向圖G=(V,R)，n=|V|，構(gòu)造矩陣P=(pij)nn，其中

pij

=1若vi

到vj可達(dá)0其他稱(chēng)P為圖G的道路矩陣（或可達(dá)矩陣）。2.8道路矩陣及Warshall算法[算法]

求給定圖G的道路矩陣P

設(shè)A為G的鄰接矩陣，B=A+A2+A3+…+An1，由[定理2-11]，bij表示由vi至vj

，長(zhǎng)度為1或2或…或n1的路徑數(shù)目，即為由vi至vj的全部路徑總和。令

pij

=1若bij

>00其他可求得G的道路矩陣P。

算法復(fù)雜度O(n4)2.8道路矩陣及Warshall算法[定義]

二值元素的邏輯運(yùn)算：

00=0，01=10=1，11=100=0，01=10=0，11=1[定義]

二值矩陣的邏輯運(yùn)算。設(shè)有矩陣A=(aij)，B=(bij)，矩陣元素值域?yàn)閧0,1}，定義運(yùn)算：2.8道路矩陣及Warshall算法[定義]

A(k)=A(k1)

A(k2)，A(1)=A注意A(k)與Ak

的區(qū)別[定理2-12]

設(shè)Ann是圖G的鄰接矩陣，若從vi

到vj存在長(zhǎng)度為l的路，則[A(l)]ij

=1，否則[A(l)]ij

=0。[證明]對(duì)l作歸納；或直接引用[定理2-11]。2.8道路矩陣及Warshall算法[Warshall算法]

設(shè)Ann是圖G的鄰接矩陣，求G的道路矩陣P。PAi1j1pjk

pjk(pji

pik)，k=1...njj+1，若jn，轉(zhuǎn)4i

i+1，若

in，轉(zhuǎn)3Stop計(jì)算復(fù)雜度O(n3)2.8道路矩陣及Warshall算法[例]

圖G的鄰接矩陣A如右，使用Warshall算法求G的道路矩陣P。[解]PA2.8道路矩陣及Warshall算法(1)i=1j

=1,2,3,4

增量方向i

=1矩陣元素處理次序：p11，

p12，

p13，

p14，

p21，

p22，……

p31，……

p41，……，p44，2.8道路矩陣及Warshall算法如：p11

=p11(p1i

pi1)=p11(p11

p11)=0p12

=p12(p2i

pi2)=p12(p21

p12)=1p13

=p13(p3i

pi3)=p13(p31

p13)=0…………結(jié)果為2.8道路矩陣及Warshall算法考察第

i次循環(huán)。第i

列的0元對(duì)應(yīng)的行，pji=0，故pjk

=pjk(pji

pik)=pjk(0

pik)=pjk；第i

列的1元對(duì)應(yīng)的行，pji=1，故pjk

=pjk(pji

pik)=pjk(1

pik)=pjkpik

，即將該行與第i行做“或”運(yùn)算。(2)i=22.8道路矩陣及Warshall算法[表上作業(yè)法]第i

次循環(huán)時(shí)，將第i

行分別“疊加”到第i列的非0元對(duì)應(yīng)的那些行，“疊加”運(yùn)算是一對(duì)行向量各個(gè)對(duì)應(yīng)元素的邏輯“或”運(yùn)算。（i=1..n）如上例：

i=22.8道路矩陣及Warshall算法非0元

i[例]

i=12.8道路矩陣及Warshall算法

i

i=22.8道路矩陣及Warshall算法

i

i=42.8道路矩陣及Warshall算法

i

i=52.8道路矩陣及Warshall算法

i[進(jìn)一步的討論]定義運(yùn)算“PQ”:(PQ)ij=pijqij，P、Q為同階矩陣。2.8道路矩陣及Warshall算法則：(PPT)ij=pij

pji

對(duì)行列重新編號(hào)得：2.8道路矩陣及Warshall算法可見(jiàn)，{v1}，{v3}以及{v2,v4,v5}的導(dǎo)出子圖分別構(gòu)成強(qiáng)連通分量。v1v2v3v4v52.8道路矩陣及Warshall算法[旅行商問(wèn)題]已知n個(gè)城市，任兩個(gè)城市之間都有無(wú)向路相通，求一條經(jīng)過(guò)所有城市一次且僅僅一次，并且總路