第七章圖論基礎(chǔ)

Graphs第1頁21二月2025第一節(jié)圖基本概念一個圖G定義為一個三元組：G=<V,E,Φ>V——非空有限集合，V中元素稱為結(jié)點(node)或

頂點(vertex)E——有限集合（能夠為空），E中元素稱為邊(edge)Φ——從E到V有序?qū)驘o序正確關(guān)聯(lián)映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)第2頁21二月2025圖基本概念圖G=<V,E,Φ>中每條邊都與圖中無序?qū)蛴行驅(qū)β?lián)絡(luò)若邊e

E與無序?qū)Y(jié)點[va,vb]相聯(lián)絡(luò)，即Φ(e)=[va,vb]

（va,vb

V）則稱e是無向邊（或邊、棱）若邊e

E與有序?qū)Y(jié)點<va,vb>相聯(lián)絡(luò)，即Φ(e)=<va,vb>

（va,vb

V）則稱e是有向邊（或?。?/p>

va是e起始結(jié)點，vb是e終止點v1v2v3(a)v1v2v3(b)v1v2v3(c)第3頁21二月2025圖基本概念若va和vb與邊（?。〆相聯(lián)結(jié)，則稱va和vb是e端結(jié)點

va和vb是鄰接結(jié)點，記作：va

adjvb

(adjoin)

也稱e關(guān)聯(lián)va和vb，或稱va和vb關(guān)聯(lián)e若va和vb不與任何邊（?。┫嗦?lián)結(jié)，則稱va和vb是非鄰接結(jié)點，記作：va

nadjvb關(guān)聯(lián)同一個結(jié)點兩條邊（弧），稱為鄰接邊（弧）關(guān)聯(lián)同一個結(jié)點及其本身邊，稱為環(huán)(cycle)，環(huán)方向沒有意義v1v2v3(a)v1v2v3(b)v1v2v3(c)第4頁21二月2025圖基本概念若將圖G中每條邊（?。┒伎醋髀?lián)結(jié)兩個結(jié)點

則G簡記為：<V,E>每條邊都是弧圖，稱為有向圖(directedgraph)（如圖b）

每條邊都是無向邊圖，稱為無向圖(undirectedgraph)

（如圖a）

有些邊是弧，有些邊是無向邊圖，稱為混合圖（如圖c）v1v2v3(a)v1v2v3(b)v1v2v3(c)第5頁21二月2025圖基本概念若圖G中任意兩個結(jié)點之間不多于一條無向邊（或不多于一條同向弧），且任何結(jié)點無環(huán)，則稱G為簡單圖（如圖c）若圖G中某兩個結(jié)點之間多于一條無向邊（或多于一條同向?。瑒t稱G為多重圖（如圖a,b）

兩個結(jié)點間多條邊（同向?。┓Q為平行邊（?。?，

平行邊（弧）條數(shù)，稱為重數(shù)v1v2v3(a)v1v2v3(b)v1v2v3(c)第6頁21二月2025圖基本概念在多重圖表示中，可在邊（?。┥蠘俗⒄麛?shù)，以表示平行邊（弧）重數(shù)把重數(shù)作為分配給邊（?。┥蠑?shù)，稱為權(quán)(weight)

將權(quán)概念普通化，使其不一定是正整數(shù)，則得到加權(quán)圖概念：給每條邊（?。┒假x予權(quán)圖，叫做加權(quán)圖(weightedgraph)

記作G=<V,E,W>，W是各邊權(quán)之和v1v2v3(a)v1v2v3(b)v1v2v3(c)1111112211第7頁21二月2025圖基本概念在無向圖G=<V,E>中，V中每個結(jié)點都與其余全部結(jié)點鄰接，即 (

va)(

vb)(va,vb

V

[va,vb]

E)，如圖(a)

則稱該圖為無向完全圖(completegraph)，記作K|V|

若|V|=n，則|E|=C

=n(n-1)/2v1v2v3(a)v1v2v3(b)2n第8頁21二月2025圖基本概念在有向圖G=<V,E>中，V中任意兩個結(jié)點間都有方向相反兩條弧，即

(

va)(

vb)(va,vb

V

<va,vb>

E∧<vb,va>

E)，如圖(a)

則稱該圖為有向完全圖，記作K|V|

若|V|=n，則|E|=P=n(n-1)v1v2v3(a)v1v2v3(b)2n第9頁21二月2025圖基本概念在圖G=<V,E>中，若有一個結(jié)點不與其它任何結(jié)點鄰接

則該結(jié)點稱為孤立結(jié)點，如圖(a)中v4僅有孤立結(jié)點圖，稱為零圖，零圖E=

，如圖(b)僅有一個孤立結(jié)點圖，稱為平凡圖(trivialgraph)，如圖(c)v1v2v3(a)v1v2v3(b)v1(c)v4第10頁21二月2025問題問題1：是否存在這種情況：25個人中，因為意見不一樣，每個人恰好與其它5個人意見一致？問題2：是否存在這種情況：2個或以上人群中，最少有2個人在此人群中朋友數(shù)一樣多？第11頁21二月2025結(jié)點次數(shù)二、結(jié)點次數(shù)定義：在有向圖G=<V,E>中，對任意結(jié)點v

V以v為起始結(jié)點弧條數(shù)，稱為出度(out-degree)

（引出次數(shù)），記為d+(v)以v為終止點弧條數(shù)，稱為入度(in-degree)

（引入次數(shù)），記為d-(v)v出度和入度和，稱為v度數(shù)(degree)

（次數(shù)），記為d(v)=d+(v)+d-(v)v1v2v3(a)第12頁21二月2025結(jié)點次數(shù)定義：在無向圖G=<V,E>中，對任意結(jié)點v

V結(jié)點v度數(shù)d(v)，等于聯(lián)結(jié)它邊數(shù)若結(jié)點v上有環(huán)，則該結(jié)點因環(huán)而增加度數(shù)2記G最大度數(shù)為：

(G)=max{d(v)|v

V}

記G最小度數(shù)為：

(G)=min{d(v)|v

V}v1v2v3(a)v1v2v3(b)v4第13頁21二月2025結(jié)點次數(shù)在圖G中任意一條邊e

E，都對其聯(lián)結(jié)結(jié)點貢獻度數(shù)2定理：在無向圖G=<V,E>中，

d(v)

=2|E|通常，將度數(shù)為奇數(shù)結(jié)點稱為奇度結(jié)點

將度數(shù)為偶數(shù)結(jié)點稱為偶度結(jié)點定理：在無向圖G=<V,E>中，奇度結(jié)點個數(shù)為偶數(shù)個第14頁21二月2025結(jié)點次數(shù)問題1：是否存在這種情況：25個人中，因為意見不一樣，每個人恰好與其它5個人意見一致？在建立一個圖模型時，一個基本問題是決定這個圖是什么

——什么是結(jié)點？什么是邊？在這個問題里，我們用結(jié)點表示對象——人；

邊通常表示兩個結(jié)點間關(guān)系——表示2個人意見一致。

也就是說，意見一致2個人（結(jié)點）間存在一條邊。第15頁21二月2025結(jié)點次數(shù)問題1：是否存在這種情況：25個人中，因為意見不一樣，每個人恰好與其它5個人意見一致？這么我們能夠知道，假如存在題目所述情況，那么每個結(jié)點都與其它5個結(jié)點相關(guān)聯(lián)。

也就是說，每個結(jié)點度為5。由定理可知：奇度結(jié)點個數(shù)為偶數(shù)個。

現(xiàn)在是否能夠得出結(jié)論了？第16頁21二月2025結(jié)點次數(shù)類似問題：晚會上大家握手言歡，握過奇數(shù)次手人數(shù)一定是偶數(shù)碳氫化合物中，氫原子個數(shù)是偶數(shù)是否有這么多面體，它有奇數(shù)個面，每個面有奇數(shù)條棱？第17頁21二月2025結(jié)點次數(shù)問題2：是否存在這種情況：兩個人或以上人群中，最少有兩個人在此人群中朋友數(shù)一樣多？以人為結(jié)點，僅當二人為朋友時，在此二人之間連一邊，得一“情誼圖”G(V,E)，設(shè)V={v1,v2,…,vn}，不妨設(shè)各結(jié)點次數(shù)為d(v1)≤d(v2)≤…≤d(vn)≤n-1。假設(shè)命題不成立，則全部些人朋友數(shù)都不一樣多，則

0≤

d(v1)<d(v2)<…<d(vn)≤n-1。第18頁21二月2025結(jié)點次數(shù)問題2：是否存在這種情況：兩個人或以上人群中，最少有兩個人在此人群中朋友數(shù)一樣多？若0≤

d(v1)<d(v2)<…<d(vn)≤n-1，則有：因為d(v1)≥0，則有d(v2)≥1，d(v3)≥2，…，d(vn)≥n-1；又因為d(vn)≤n-1，所以：d(vn)=n-1因為d(vn)=n-1，則每個結(jié)點皆與vn相鄰，則d(v1)≥1。于是有：d(v2)≥2，d(v3)≥3，…，d(vn)≥n，矛盾。故假設(shè)不成立，即d(v1)<d(v2)<…<d(vn)中最少有一個等號成立，命題成立。第19頁21二月2025結(jié)點次數(shù)定義：在無向圖G=<V,E>中，若每個結(jié)點度數(shù)都是k，即 (

v)(v

V

d(v)=k)，則稱G為k度正則圖(regulargraph)v1v2v6v33度正則圖v4v5v7v8v9v103度正則圖v1v5v6v2v3v4第20頁21二月2025子圖三、子圖定義：給定無向圖G1=<V1,E1>，G2=<V2,E2>若V2

V1，E2

E1，則稱G2是G1子圖(subgraph)，

記作G2

G1若V2

V1，E2

E1，且E2≠

E1，則稱G2是G1真子圖，記作G2

G1若V2=

V1，E2

E1，則稱G2是G1生成子圖(spanningsubgraph)，記作G2

G1V2=

V1第21頁21二月2025子圖比如：v2v1(a)v3v4v5(a)真子圖v2v3v4v5(a)生成子圖v2v3v4v5v1第22頁21二月2025子圖定義：對于圖G=<V,E>，G1=<V,E>=G，G2=<V,

>

G1和G2都是G生成子圖，稱為平凡生成子圖定義：設(shè)G2=<V2,E2>是G1=<V1,E1>子圖對任意結(jié)點u,v

V2，若有[u,v]

E1，則有[u,v]

E2，

則G2由V2唯一地確定，則稱G2是V2誘導(dǎo)子圖

記作G[V2]，或G2=<V2>若G2中無孤立結(jié)點，且由E2唯一地確定，則稱

G2是E2誘導(dǎo)子圖，記作G[E2]，或G2=<E2>第23頁21二月2025子圖比如：v2v1G=<V,E>v3v4v5G’=<V’,E’>

V’或E’誘導(dǎo)子圖v2v3v4v5第24頁21二月2025補圖定義：

設(shè)G1=<V1,E1>和G2=<V2,E2>是G=<V,E>子圖，

若E2=E-E1，且G2是E2誘導(dǎo)子圖，即G2=<E2>

則稱G2是相對于GG1補圖第25頁21二月2025補圖 圖G1和G2互為相對于G補圖G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v5第26頁21二月2025補圖定義：

給定圖G1=<V,E1>，若存在圖G2=<V,E2>

且E1

E2=

，及圖<V,E1

E2

>是完全圖

則稱G2是相對于完全圖G1補圖，記作G2=G1第27頁21二月2025補圖

G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v1第28頁21二月2025圖同構(gòu)四、圖同構(gòu)定義：

給定圖G1=<V1,E1>，G2=<V2,E2>

若存在雙射函數(shù)f:V1

V2，使得對于任意u,v

V1

有 [u,v]

E1[f(u),f(v)]

E2

（或<u,v>

E1<f(u),f(v)>

E2）

則稱G1與G2同構(gòu)(isomorphic)，記作G1

G2第29頁21二月2025圖同構(gòu)例7.1.1證實下面兩個圖G1=<V1,E1>，G2=<V2,E2>同構(gòu)證實：V1={v1,v2,v3,v4},V2={a,b,c,d}結(jié)構(gòu)雙射函數(shù)f:V1

V2，f(v1)=a，f(v2)=b

f(v3)=c，f(v4)=d可知，邊[v1,v2],[v2,v3],[v3,v4],

[v4,v1]被分別映射成[a,b],

[b,c],[c,d],[d,a]，故G1

G2v2v1G1v3v4badcG2第30頁21二月2025圖同構(gòu)例7.1.2證實下面兩個有向圖是同構(gòu)。G1eabcd證實：如圖所表示，G1=<V1,E1>，G2=<V2,E2>，結(jié)點編號如圖所表示。 結(jié)構(gòu)函數(shù)f:V1

V2，使得f(a)=1,f(b)=3,f(c)=4,f(d)=5,f(e)=2 則<a,e>,<b,a>,<b,c>,<c,e>,<d,a>,<d,c>,<e,b>,<e,d>被分別映射成<1,2>,<3,1>,<3,4>,<4,2>,<5,1>,<5,4>,<2,3>,<2,5>

故f是雙射函數(shù)，所以G1與G2同構(gòu)G131245第31頁21二月2025圖同構(gòu)能夠給出圖同構(gòu)必要條件：結(jié)點數(shù)相等邊數(shù)相等度數(shù)相等結(jié)點數(shù)相等要注意是，這不是充分條件第32頁21二月2025圖同構(gòu)例7.1.3證實下面兩個無向圖是不一樣構(gòu)G1v1v2v3v4v5v6v7v8G2abcdefghv1是3度結(jié)點，故f(v1)只能是c或d或g或h。若f(v1)=c，因為v2、v4和v5與v1鄰接，所以f(v2)、f(v4)和f(v5)應(yīng)該分別為與c鄰接b、d和g。不過，v2、v4和v5中，只有一個3度結(jié)點，而b、d、g中卻有2個3度結(jié)點，故f(v1)≠c。同理可說明，f(v1)也不可能是d、g和h。所以這么f是不存在。所以G1和G2是不一樣構(gòu)。第33頁21二月2025第二節(jié)路(鏈)與回路(圈)一、路(鏈)與回路(圈)定義：給定圖G=<V,E>，令v0,v1,…,vm

V，e1,e2,…,em

E稱交替序列v0e1v1

e2

v2…emvm為連接v0到vm鏈（路）稱v0和vm為鏈（路）始結(jié)點和終止點鏈長度為邊（?。?shù)目m若v0=vm，該鏈（路）稱為圈（回路,circuit）第34頁21二月2025鏈和圈在鏈中：若任意ei只出現(xiàn)一次，則稱該鏈（路）為簡單鏈（路）若任意vi只出現(xiàn)一次，則稱該鏈（路）為基本鏈（路）基本鏈必定是簡單鏈在圈中：若任意ei只出現(xiàn)一次，則稱該圈（回路）為簡單圈（回路）若任意vi只出現(xiàn)一次，則稱該圈（回路）為基本圈（回路）第35頁21二月2025鏈和圈例7.2.1下列圖中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1e1v2e7v5)

也能夠表示為：P1=(e1e7)

是一個基本鏈，也是一個簡單鏈P2=(v2e2v3e3v3e4v1e1v2)

也能夠表示為：P2=(e2e3e4e1

)

是一個簡單圈，但不是基本圈P3=(v4e6v2e7v5e8v4e6v2e2v3)是一個鏈P4=(v2e7v5e8v4e6v2)是一個基本圈，也是一個簡單圈第36頁21二月2025鏈和圈鏈和圈能夠只用邊序列表示

上例中：(v2e2v3e3v3e4v1e1v2)也可表示為(e2e3e4e1)

(v4e6v2e7v5e8v4e6v2e2v3)也可表示為(e6e7e8e6e2)對于簡單圖來說，鏈和圈能夠僅用結(jié)點序列表示v3v1v4v5v2e1e2e4e5e6e3e8圖中：

(v2e2v3e4v1e1v2e3v5e8v4)

可表示為(e2e4e1e3e8)

也可表示為(v2v3v1v2v5v4)第37頁21二月2025鏈和圈定理：在一個圖中，若從結(jié)點vi到結(jié)點vj存在一條鏈（路）， 則必有一條從vi到vj基本鏈（路）證實：1)若從vi到vj給定鏈本身就是基本鏈，定理成立2)若從vi到vj給定鏈不是基本鏈，則最少含有一個結(jié)點vk，它在該鏈中最少出現(xiàn)兩次以上。也就是說，經(jīng)過vk有一個圈

，于是能夠從原有鏈中去除

中全部出現(xiàn)邊（?。?。對于原鏈中所含全部圈都做此處理，最終將得到一條基本鏈（路）第38頁21二月2025鏈和圈問題：在一個圖中，若從結(jié)點vi到結(jié)點vj存在一個圈，

則必有一個從vi到vj基本圈嗎？例7.2.2若u和v是一個圈上兩個結(jié)點，u和v一定是某個基本圈上結(jié)點嗎？(習(xí)題7-16)答：不一定vaudcb本圖中，u和v在一個圈上，不過卻不在一個基本圈上第39頁21二月2025鏈和圈定理：在一個含有n個結(jié)點圖中，任何基本鏈（路）長度小于n-1任何基本圈（回路）長度小于n證實：1)依據(jù)基本鏈定義可知，出現(xiàn)在基本鏈中結(jié)點都是不一樣。所以在長度為m基本鏈中，不一樣結(jié)點數(shù)為m+1又因為圖中僅有n個結(jié)點，故m+1≤n，即m≤n-12)依據(jù)基本圈定義可知，長度為k基本圈中，不一樣結(jié)點數(shù)為k，圖中共有n個結(jié)點，所以k≤n第40頁21二月2025可達二、連通圖定義：

在一個圖中，若從vi到vj存在任何一條鏈

則稱從vi到vj是可達(accessible)，簡稱vi可達vj要求：每個結(jié)點vi到本身都是可達第41頁21二月2025連通無向圖（一）連通無向圖對于無向圖G=<V,E>而言，可證實“可達性”是一個___關(guān)系。它對V給出一個劃分，每個塊中元素形成一個誘導(dǎo)子圖。兩個結(jié)點間是可達，當且僅當它們屬于同一個子圖

稱這么子圖為G連通分圖，G連通分圖個數(shù)記為

(G)若G中只有一個連通分圖，則稱G是連通圖(即任意兩結(jié)點可達)

不然稱G為非連通圖，或分離圖等價第42頁21二月2025連通無向圖定義：在無向圖G=<V,E>中若任意兩個結(jié)點可達，則稱G是連通(connected)，

稱G為連通無向圖；

不然稱G是非連通，稱G為非連通圖或分離圖。若G子圖G’是連通，且不存在包含G’更大G

子圖G’’是連通，則稱G’是G連通分圖(connectedcomponents)，簡稱分圖。G中連通分圖個數(shù)記為

(G)。第43頁21二月2025連通無向圖例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是連通圖，

(G1)=1G2是非連通圖，

(G2)=2第44頁21二月2025連通無向圖定義：從圖G=<V,E>中刪除結(jié)點集S，是指V-SE-{與S中結(jié)點相連結(jié)邊}而得到子圖，記做G-SG-{v3}v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v2第45頁21二月2025連通無向圖定義：從圖G=<V,E>中刪除結(jié)點集S，是指V-SE-{與S中結(jié)點相連結(jié)邊}而得到子圖，記做G-SG-{v3}v1v4v5v2G第46頁21二月2025連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v2第47頁21二月2025連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge2e5e6e7第48頁21二月2025連通無向圖定義：給定連通無向圖G=<V,E>，S

V若

(G-S)>

(G)=1且對任意T

S，

(G-T)=

(G)則稱S是G一個分離結(jié)點集(cut-setofnodes)若S中僅含有一個元素v，則稱v是G割點(cut-node)第49頁21二月2025連通無向圖例7.2.4 G以下列圖所表示，S={v1,v3}v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S

(G)=1，

(G-S)=2

(G-S)>

(G)第50頁21二月2025連通無向圖例7.2.4 G以下列圖所表示，S={v1,v3}v2v1v5v6v4Gv3

(G)=1，

(G-S)=2

(G-S)>

(G)

(G-{v1})=1v2v5v6v4G-{v1}v3第51頁21二月2025連通無向圖例7.2.4 G以下列圖所表示，S={v1,v3}v2v1v5v6v4Gv3

(G)=1，

(G-S)=2

(G-S)>

(G)

(G-{v1})=1v2v1v5v6v4G-{v3}

(G-{v3})=1第52頁21二月2025連通無向圖例7.2.4 G以下列圖所表示，S={v1,v3}v2v1v5v6v4Gv3v2v5v6v4G-S

(G)=1，

(G-S)=2

(G-S)>

(G)

(G-{v1})=1

(G-{v3})=1S是G分離結(jié)點集第53頁21二月2025連通無向圖例7.2.5 G以下列圖所表示，S={v2}v1v4v5v3Gv2

(G)=1，

(G-S)=2

(G-S)>

(G)v1v4v5v3G-Sv2是G割點不存在其它G割點第54頁21二月2025連通無向圖定義：給定連通無向圖G=<V,E>，T

E若

(G-T)>

(G)=1且對任意F

T，

(G-F)=

(G)則稱T是G一個分離邊集(cut-setofedges)若T中僅含有一個元素e，則稱e是G割邊(cut-edge)，或橋第55頁21二月2025連通無向圖例7.2.6 G以下列圖所表示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3第56頁21二月2025連通無向圖例7.2.6 G以下列圖所表示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-{e1}v2e4e2e3

(G-{e1})=1第57頁21二月2025連通無向圖例7.2.6 G以下列圖所表示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3

(G-{e1})=1

(G-{e2})=1v1v3v4G-{e2}v2e1e4e3第58頁21二月2025連通無向圖例7.2.6 G以下列圖所表示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3

(G-{e1})=1

(G-{e2})=1T是G分離邊集第59頁21二月2025連通無向圖例7.2.7 G以下列圖所表示，T={e1}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e2e3v1v3v4G-Tv2e2e3e1是G割邊e2和e3都是G割邊第60頁21二月2025連通無向圖定義：對連通非平凡圖G=<V,E>，稱

(G)=min{|S||S是G分離結(jié)點集}

為G結(jié)點連通度(node-connectivity)

它表明產(chǎn)生分離圖需要刪去結(jié)點最少數(shù)目對分離圖G而言，

(G)=0對存在割點連通圖G而言，

(G)=1S

V第61頁21二月2025連通無向圖例7.2.8 求G1和G2結(jié)點連通度v2v1v5v6v4G1v3

(G1)=2

(G2)=1v1v4v5v3G2v2第62頁21二月2025連通無向圖定義：對連通非平凡圖G=<V,E>，稱

(G)=min{|T||T是G分離邊集}

為G邊連通度(edge-connectivity)

它表明產(chǎn)生分離圖需要刪去邊最少數(shù)目對分離圖G而言，

(G)=0對存在割邊連通圖G而言，

(G)=1對無向完全圖Kn，

(Kn)=?T

En-1第63頁21二月2025連通無向圖例7.2.9 求G1和G2邊連通度

(G1)=2

(G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e3第64頁21二月2025連通無向圖定理：對于任何一個無向圖G，有

(G)≤

(G)≤

(G)證實：1)若G是分離圖，則

(G)=

(G)=0，而

(G)≥02)若G是連通圖，先證實

(G)≤

(G)若G是平凡圖，則

(G)=0=

(G)若G不是平凡圖，則當刪去全部聯(lián)結(jié)一個含有最小度結(jié)點邊（除了環(huán)）后，便產(chǎn)生了一個分離圖，所以

(G)≤

(G)再證實

(G)≤

(G)

若

(G)＝1，則G存在一個割邊，顯然

(G)=

(G)=1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v3v4G–{v1}v2e3第65頁21二月2025連通無向圖若

(G)≥2，則刪去某

(G)條邊后，G就成為分離圖若只刪除

(G)-1條邊，則仍得到連通圖且存在一割邊e=[u,v]對于

(G)-1條邊中每一條邊，選取一個不一樣于u和v結(jié)點，把這些結(jié)點刪去，將必須最少刪去

(G)-1條邊若這么會產(chǎn)生分離圖，則

(G)≤

(G)-1<

(G)若這么產(chǎn)生仍是連通圖且e是割邊，再刪除結(jié)點u或v必將產(chǎn)生分離圖，所以

(G)≤

(G)v1v3v4Gv2e1e4e2e3v1v3v4G–{v2}e2e3v1v4G–{v3}總而言之，有

(G)≤

(G)≤

(G)第66頁21二月2025連通無向圖定理：一個連通無向圖G中結(jié)點v是割點，充要條件是存在兩個結(jié)點u和w，使得聯(lián)結(jié)u和w每條鏈都經(jīng)過v證實：1)充分性：若G中聯(lián)結(jié)u和w每條鏈都經(jīng)過v，刪去v，則在子圖G-{v}中，u和w必定不可達，故v是G割點2)必要性：若v是G割點，刪去v，則子圖G-{v}中最少有兩個連通分圖G1=<V1,E1>和G2=<V2,E2>

，任取兩個結(jié)點

u

V1，w

V2，u和w不可達。故G中聯(lián)結(jié)u和w每條鏈必經(jīng)過v第67頁21二月2025連通無向圖同理能夠證實：定理：一個連通無向圖G中邊e是割邊，充要條件是存在兩個結(jié)點u和w，使得聯(lián)結(jié)u和w每條鏈都經(jīng)過e定理：一個連通無向圖G中邊e是割邊，充要條件是e不包含在G任何基本圈中證實：教材P172（定理7.8)第68頁21二月2025烏拉姆猜測（1929）左右兩張相片，捂住左邊相片一部分，也捂住右邊相片對應(yīng)部分，比如都捂住左眼，能看到相片大部分形象一致；再分別捂住左右相片另一個對應(yīng)部分，比如右耳，結(jié)果能看到相片大部分依然一致。如此輪番地觀察各次對應(yīng)暴露部分，都會看到相同形象，那么誰都會相信這兩張照片是同一個人或?qū)\生弟兄留影。數(shù)學(xué)描述：有圖G1={V1,E1}和G2={V2,E2}，

V1={v1,v2,…,vn}，V2={u1,u2,…,un}（n≥3）。

假如G1-{vi}≌G2-{ui}，i=1,2,…,n，則G1≌G2第69頁21二月2025連通有向圖（二）連通有向圖對于有向圖G=<V,E>而言，結(jié)點間可達性不再是等價關(guān)系，它僅僅是自反和可傳遞，普通不是對稱定義：對于給定有向圖G，要略去G中每條邊方向，

便得到一個無向圖G’，稱G’是G基礎(chǔ)圖第70頁21二月2025連通有向圖定義：在簡單有向圖G中，若任何兩個結(jié)點間都是可達，則稱G是強連通若任何兩個結(jié)點間，最少是從一個結(jié)點可達另一個結(jié)點，則稱G是單向連通若G基礎(chǔ)圖是連通，則稱G是弱連通第71頁21二月2025連通有向圖例7.2.10判斷G1、G2和G3是強連通？單向連通？弱連通？G1是強連通v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是單向連通G3是弱連通第72頁21二月2025連通有向圖由定義可知：若G是強連通，則它必定是單向連通

反之未必真若G是單向連通，則它必是弱連通

反之未必真第73頁21二月2025連通有向圖定理：有向圖G是強連通，當且僅當G中有一回路，它最少經(jīng)過每個結(jié)點一次證實：1)充分性：若G中存在一條回路，它最少經(jīng)過每個結(jié)點一回，則G中任何兩個結(jié)點都是相互可達，所以G是強連通。2)必要性：若G是強連通，則G中任何兩個結(jié)點都是相互可達，所以能夠做出一條回路經(jīng)過G中全部結(jié)點，不然，必有某結(jié)點v不在該回路上，v與回路上各結(jié)點不可能都相互可達。與G是強連通矛盾第74頁21二月2025連通有向圖定義：在簡單有向圖G中含有強連通性質(zhì)極大子圖，稱為強分圖含有單向連通性質(zhì)極大子圖，稱為單向分圖含有弱連通性質(zhì)極大子圖，稱為弱分圖第75頁21二月2025連通有向圖例7.2.11 求G強分圖、單向分圖和弱分圖v3v2v1Gv4v5v6v3v2v1v4v5v6G強分圖有：定理：簡單有向圖G中任意一個結(jié)點，恰位于一個強分圖中第76頁21二月2025連通有向圖定理：簡單有向圖G中任意一個結(jié)點，恰位于一個強分圖中證實：由強分圖定義可知，G中每個結(jié)點位于一個強分圖中假設(shè)G中存在結(jié)點v位于兩個強分圖G1和G2中則由強分圖定義可知，G1中每個結(jié)點與v相互可達，G2中每個結(jié)點也與v相互可達故G1中每個結(jié)點與G2中每個結(jié)點經(jīng)過v，能夠相互可達，這與G1和G2是兩個強分圖矛盾所以G中每個結(jié)點只能位于一個強分圖中第77頁21二月2025連通有向圖例7.2.11 求G強分圖、單向分圖和弱分圖G單向分圖有：v3v2v1Gv4v5v6v3v2v1v4v5v5v6定理：簡單有向圖G中每個結(jié)點和每條弧,最少位于一個單向分圖中第78頁21二月2025連通有向圖例7.2.11 求G強分圖、單向分圖和弱分圖G弱分圖有：v3v2v1Gv4v5v6v3v2v1v4v5v6定理：簡單有向圖G中每個結(jié)點和每條弧

恰位于一個弱分圖中第79頁21二月2025結(jié)點間距離三、結(jié)點間距離定義：在圖G中，若結(jié)點u可達結(jié)點v，它們之間可能存在不止一條鏈（路）。

在全部鏈中，最短鏈長度稱為結(jié)點u和v之間距離

（或短程線、測地線）。記做：d<u,v>第80頁21二月2025結(jié)點間距離距離滿足下面性質(zhì)：d<u,v>≥0d<u,u>=0d<u,v>+d<v,w>≥d<u,w>若u不可達v，則d<u,v>=+

即使u和v相互可達，d<u,v>未必等于d<v,u>

第81頁21二月2025有向圖在計算機中應(yīng)用四、有向圖在計算機中應(yīng)用這里給出一個簡單有向圖在計算機中應(yīng)用——

利用資源分配圖來糾正和發(fā)覺死鎖第82頁21二月2025有向圖在計算機中應(yīng)用在多道程序計算機系統(tǒng)中，同一時間內(nèi)有多個程序需要同時執(zhí)行。每個程序都共享計算機資源：如CPU、內(nèi)存、外存、輸入設(shè)備、編譯系統(tǒng)等，操作系統(tǒng)將對這些資源分配給各個程序。當一個程序需要使用某種資源時候，要向操作系統(tǒng)發(fā)出請求，操作系統(tǒng)必須確保這個請求得到滿足，才能運行該程序第83頁21二月2025有向圖在計算機中應(yīng)用對資源請求可能發(fā)生沖突，發(fā)生死鎖。比如：程序P1占有資源r1，請求資源r2程序P2占有資源r2，請求資源r1有沖突請求必須要處理，能夠利用有向圖來模擬對資源請求，從而幫助發(fā)覺和糾正“死鎖”狀態(tài)第84頁21二月2025有向圖在計算機中應(yīng)用令Pt={P1,P2,P3,P4}是t時刻運行程序集合

Rt={r1,r2,r3,r4}是t時刻所需要資源集合P1占有資源r4，請求資源r1P2占有資源r1，請求資源r2和r3P3占有資源r2，請求資源r3P4占有資源r3，請求資源r1和r4可得到資源分配圖G如圖所表示r4r3r2r1P1P3P2P2P4P4可證：t時刻系統(tǒng)處于死鎖狀態(tài)

G中包含多于一個結(jié)點強分圖第85頁21二月2025有向圖在計算機中應(yīng)用t時刻系統(tǒng)處于死鎖狀態(tài)

G中包含多于一個結(jié)點強分圖處理方法：

使G中每個強分圖中

都是單個結(jié)點r4r3r2r1P1P3P2P2P4P4r4r3r2r1P1P3P2P2第86頁21二月20253x+1猜測（卡拉茲）20世紀30年代，漢堡大學(xué)卡拉茲（Callatz）提出一個猜測：x0是一個自然數(shù)，若x0是偶數(shù)，則取x1=x0/2，若x0是奇數(shù)，則取x1=(3x0+1)/2。將x1應(yīng)用上述規(guī)則得到x2，……如此進行下去，則抵達某一步，xk=1。東京大學(xué)N.永內(nèi)達（NabuoYoneda）用計算機檢驗了全部不超出240≈1.2×1012自然數(shù)，結(jié)果都符合卡拉茲猜測。第87頁21二月20253x+1猜測（卡拉茲）假如把一批自然數(shù)放在最高層，用3x+1問題規(guī)則算出第二層值，繼而算出第三層值……。圖中結(jié)點是自然數(shù)，當數(shù)1算出數(shù)2時，則在圖上畫上有向邊<數(shù)1,數(shù)2>，得到有向圖稱為卡拉茲有向圖，如圖所表示。3x+1猜測中，卡拉茲圖最底層結(jié)點是1。第88頁21二月2025第三節(jié)圖矩陣表示一、圖矩陣表示定義：給定簡單圖G=<V,E>，V={v1,v2,…,vn}

V中結(jié)點按照下標由小到大編序（編序與矩陣形式有親密關(guān)系），則n階方陣AG=(aij)稱為圖G鄰接矩陣(adjacencymatrix)。其中：aij= i,j=1,2,…,n1 viadjvj

0 vinadjvj第89頁21二月2025鄰接矩陣例7.3.1圖G=<V,E>如圖所表示v4v5v3v2v10111110100110101010110010AG=G鄰接矩陣為：0100110101010110010111110AG’=G’鄰接矩陣變?yōu)椋簐3v4v2v1v5若G’中結(jié)點編序以下列圖所表示第90頁21二月2025鄰接矩陣例7.3.2圖G=<V,E>如圖所表示0101001010010100AG=G鄰接矩陣為：v1v3v4v2若G’中結(jié)點編序以下列圖所表示v4v3v1v20100001010011100AG’=G’鄰接矩陣變?yōu)椋旱?1頁21二月2025鄰接矩陣對于僅僅結(jié)點編序不一樣圖，是同構(gòu)

它們鄰接矩陣也是相同G1

G2

存在置換矩陣P，使得

AG2=P-1AG1P對于由結(jié)點編序不一樣引發(fā)鄰接矩陣不一樣將被忽略

任取圖任意一個鄰接矩陣作為該圖矩陣表示第92頁21二月2025鄰接矩陣圖G鄰接矩陣AG能夠展示圖G一些性質(zhì)：若鄰接矩陣AG元素全是零，則G是若鄰接矩陣AG元素主對角線上全是0，其它元素全是1，

則G是無向圖G鄰接矩陣AG是在簡單有向圖鄰接矩陣中，第i行元素是由結(jié)點vi出發(fā)弧所確

定，故第i行元素為1數(shù)目，等于vi

，即d+(vi)=

aik

第j列元素是由抵達結(jié)點vj弧所確定，故第j列元素為1數(shù)目，

等于vj

，即d-(vj)=

akjn

k=1n

k=1零圖連通簡單完全圖對稱矩陣出度入度第93頁21二月2025鄰接矩陣定理：設(shè)A為簡單圖G鄰接矩陣，則An中i行j列元素

aijn等于G中聯(lián)結(jié)vi和vj長度為n鏈（路）數(shù)目證實：1)當n=1時，An=A1=A，定理成立2)設(shè)n=k時定理成立，即aijk為G中聯(lián)結(jié)vi和vj長度為k鏈數(shù)目3)當n=k+1時，An=Ak+1=Ak×A，即aijk+1=

airk×

arj

依據(jù)假設(shè)可知，airk為G中聯(lián)結(jié)vi和vr長度為k鏈數(shù)目，arj為G中聯(lián)結(jié)vr和vj長度為1鏈數(shù)目，所以aijk+1為G中聯(lián)結(jié)vi和vj長度為k+1鏈數(shù)目第94頁21二月2025鄰接矩陣例7.3.3圖G=<V,E>如圖所表示，求A,A2,A3,A40101001010010100A=v1v3v4v20110100102010010A2=1011020101201001A3=1202012020120201A4=第95頁21二月2025鄰接矩陣由上面定理可知：

若要判斷圖G中結(jié)點vi到vj是否可達，能夠利用G鄰接矩陣A，

計算A,A2,A3,…,An,…

若發(fā)覺某個Ar（r是正整數(shù)）中aijr

≥1，則表明vi到vj可達。由上一節(jié)定理可知：

對于含有n個結(jié)點圖G，任何基本鏈（路）長度小于，

任何基本圈（回路）長度小于所以，僅考慮aijr（1≤r≤n）即可n-1n第96頁21二月2025鄰接矩陣所以，只要計算Bn=(bij)=A+A2+A3+…+An

Bn

中元素bij表示vi到vj長度小于等于n不一樣路徑總數(shù)bij≠

0時，vi可達vj；

若i=j，則說明存在經(jīng)過vi回路bij＝

0時，vi不可達vj；

若i=j，則說明不存在經(jīng)過vi回路第97頁21二月2025鄰接矩陣例7.3.4圖G=<V,E>如圖所表示，求Bnv1v3v4v2Bn=A+A2+A3+A40110100102010010+1011020101201001+1202012020120201+0101001010010100=2424133233341312=第98頁21二月2025鄰接矩陣問題：怎樣判斷某無向圖G是否為連通圖？求出Bn=(bij)=A+A2+A3+…+An若有某個bij為0(i≠j)，則說明結(jié)點vi和vj處于不一樣連通分圖中，圖G為分離圖；

不然G為連通圖（即非主對角線上元素都不為0）。思索：主對角線上元素bii表示什么？第99頁21二月2025可達矩陣若關(guān)心只是結(jié)點間可達性或結(jié)點間是否有鏈存在

至于存在多少條鏈以及長度為多少無關(guān)緊要

則能夠使用可達矩陣P=(pij)來表示結(jié)點間可達性：pij= 1, vi

可達vj

0, vi

不可達vj第100頁21二月2025可達矩陣可達矩陣P=(pij)計算之一：經(jīng)過Bn

可令Bn=(bij)=A+A2+A3+…+An

再將Bn中非零元素改為1，零元素不變，即可得到P

pij= 1, bij≠

0

0, bij＝

0注意：可達矩陣中，主對角線元素aii只表現(xiàn)了是否存在經(jīng)過

結(jié)點vi圈，并不描述結(jié)點到本身可達性。第101頁21二月2025可達矩陣例7.3.5圖G=<V,E>如圖所表示，求可達矩陣Pv1v3v4v2Bn=A+A2+A3+A42424133233341312=1111111111111111P=由P可知：G中任意兩個結(jié)點彼此可達任意結(jié)點處都有圈存在

G是強連通圖第102頁21二月2025可達矩陣怎樣判定有向圖G是否為強連通圖？強連通圖G可達矩陣P中全部元素aij都為1（aii是否必定為1？）怎樣判定有向圖G是否為單向連通圖