離散數(shù)學(xué)-圖論基礎(chǔ)課件

第七章圖論基礎(chǔ)

Graphs離散數(shù)學(xué)-圖論基礎(chǔ)第一節(jié)圖的基本概念一個(gè)圖G定義為一個(gè)三元組：G=<V,E,Φ>V——非空有限集合，V中的元素稱為結(jié)點(diǎn)(node)或

頂點(diǎn)(vertex)E——有限集合（可以為空），E中的元素稱為邊(edge)Φ——從E到V的有序?qū)驘o序?qū)Φ年P(guān)聯(lián)映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)17三月2024圖的基本概念圖G=<V,E,Φ>中的每條邊都與圖中的無序?qū)蛴行驅(qū)β?lián)系若邊e

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

（va,vb

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

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

（va,vb

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

va是e的起始結(jié)點(diǎn)，vb是e的終結(jié)點(diǎn)v1v2v3(a)v1v2v3(b)v1v2v3(c)17三月2024圖的基本概念若va和vb與邊（?。〆相聯(lián)結(jié)，則稱va和vb是e的端結(jié)點(diǎn)

va和vb是鄰接結(jié)點(diǎn)，記作：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é)點(diǎn)，記作：va

nadjvb關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊（?。?，稱為鄰接邊（?。╆P(guān)聯(lián)同一個(gè)結(jié)點(diǎn)及其自身的邊，稱為環(huán)(cycle)，環(huán)的方向沒有意義v1v2v3(a)v1v2v3(b)v1v2v3(c)17三月2024圖的基本概念若將圖G中的每條邊（?。┒伎醋髀?lián)結(jié)兩個(gè)結(jié)點(diǎn)

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

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

（如圖a）

有些邊是弧，有些邊是無向邊的圖，稱為混合圖（如圖c）v1v2v3(a)v1v2v3(b)v1v2v3(c)17三月2024圖的基本概念若圖G中的任意兩個(gè)結(jié)點(diǎn)之間不多于一條無向邊（或不多于一條同向?。?，且任何結(jié)點(diǎn)無環(huán)，則稱G為簡(jiǎn)單圖（如圖c）若圖G中某兩個(gè)結(jié)點(diǎn)之間多于一條無向邊（或多于一條同向?。?，則稱G為多重圖（如圖a,b）

兩個(gè)結(jié)點(diǎn)間的多條邊（同向?。┓Q為平行邊（?。?，

平行邊（弧）的條數(shù)，稱為重?cái)?shù)v1v2v3(a)v1v2v3(b)v1v2v3(c)17三月2024圖的基本概念在多重圖的表示中，可在邊（?。┥蠘?biāo)注正整數(shù)，以表示平行邊（?。┑闹?cái)?shù)把重?cái)?shù)作為分配給邊（弧）上的數(shù)，稱為權(quán)(weight)

將權(quán)的概念一般化，使其不一定是正整數(shù)，則得到加權(quán)圖的概念：給每條邊（弧）都賦予權(quán)的圖，叫做加權(quán)圖(weightedgraph)

記作G=<V,E,W>，W是各邊權(quán)之和v1v2v3(a)v1v2v3(b)v1v2v3(c)111111221117三月2024圖的基本概念在無向圖G=<V,E>中，V中的每個(gè)結(jié)點(diǎn)都與其余的所有結(jié)點(diǎn)鄰接，即 (

va)(

vb)(va,vb

V

[va,vb]

E)，如圖(a)

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

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

=n(n-1)/2v1v2v3(a)v1v2v3(b)2n17三月2024圖的基本概念在有向圖G=<V,E>中，V中的任意兩個(gè)結(jié)點(diǎn)間都有方向相反的兩條弧，即

(

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)2n17三月2024圖的基本概念在圖G=<V,E>中，若有一個(gè)結(jié)點(diǎn)不與其他任何結(jié)點(diǎn)鄰接

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

，如圖(b)僅有一個(gè)孤立結(jié)點(diǎn)的圖，稱為平凡圖(trivialgraph)，如圖(c)v1v2v3(a)v1v2v3(b)v1(c)v417三月2024問題問題1：是否存在這種情況：25個(gè)人中，由于意見不同，每個(gè)人恰好與其他5個(gè)人意見一致？問題2：是否存在這種情況：2個(gè)或以上的人群中，至少有2個(gè)人在此人群中的朋友數(shù)一樣多？17三月2024結(jié)點(diǎn)的次數(shù)二、結(jié)點(diǎn)的次數(shù)定義：在有向圖G=<V,E>中，對(duì)任意結(jié)點(diǎn)v

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

（引出次數(shù)），記為d+(v)以v為終結(jié)點(diǎn)的弧的條數(shù)，稱為入度(in-degree)

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

（次數(shù)），記為d(v)=d+(v)+d-(v)v1v2v3(a)17三月2024結(jié)點(diǎn)的次數(shù)定義：在無向圖G=<V,E>中，對(duì)任意結(jié)點(diǎn)v

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

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

V}

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

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

V}v1v2v3(a)v1v2v3(b)v417三月2024結(jié)點(diǎn)的次數(shù)在圖G中的任意一條邊e

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

d(v)

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

將度數(shù)為偶數(shù)的結(jié)點(diǎn)稱為偶度結(jié)點(diǎn)定理：在無向圖G=<V,E>中，奇度結(jié)點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)17三月2024結(jié)點(diǎn)的次數(shù)問題1：是否存在這種情況：25個(gè)人中，由于意見不同，每個(gè)人恰好與其他5個(gè)人意見一致？在建立一個(gè)圖模型時(shí)，一個(gè)基本問題是決定這個(gè)圖是什么

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

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

也就是說，意見一致的2個(gè)人（結(jié)點(diǎn)）間存在一條邊。17三月2024結(jié)點(diǎn)的次數(shù)問題1：是否存在這種情況：25個(gè)人中，由于意見不同，每個(gè)人恰好與其他5個(gè)人意見一致？這樣我們可以知道，如果存在題目所述情況，那么每個(gè)結(jié)點(diǎn)都與其他5個(gè)結(jié)點(diǎn)相關(guān)聯(lián)。

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

現(xiàn)在是否能夠得出結(jié)論了？17三月2024結(jié)點(diǎn)的次數(shù)類似問題：晚會(huì)上大家握手言歡，握過奇數(shù)次手的人數(shù)一定是偶數(shù)碳?xì)浠衔镏?，氫原子個(gè)數(shù)是偶數(shù)是否有這樣的多面體，它有奇數(shù)個(gè)面，每個(gè)面有奇數(shù)條棱？17三月2024結(jié)點(diǎn)的次數(shù)問題2：是否存在這種情況：兩個(gè)人或以上的人群中，至少有兩個(gè)人在此人群中的朋友數(shù)一樣多？以人為結(jié)點(diǎn)，僅當(dāng)二人為朋友時(shí)，在此二人之間連一邊，得一“友誼圖”G(V,E)，設(shè)V={v1,v2,…,vn}，不妨設(shè)各結(jié)點(diǎn)的次數(shù)為d(v1)≤d(v2)≤…≤d(vn)≤n-1。假設(shè)命題不成立，則所有人的朋友數(shù)都不一樣多，則

0≤

d(v1)<d(v2)<…<d(vn)≤n-1。17三月2024結(jié)點(diǎn)的次數(shù)問題2：是否存在這種情況：兩個(gè)人或以上的人群中，至少有兩個(gè)人在此人群中的朋友數(shù)一樣多？若0≤

d(v1)<d(v2)<…<d(vn)≤n-1，則有：由于d(v1)≥0，則有d(v2)≥1，d(v3)≥2，…，d(vn)≥n-1；又因?yàn)閐(vn)≤n-1，所以：d(vn)=n-1因?yàn)閐(vn)=n-1，則每個(gè)結(jié)點(diǎn)皆與vn相鄰，則d(v1)≥1。于是有：d(v2)≥2，d(v3)≥3，…，d(vn)≥n，矛盾。故假設(shè)不成立，即d(v1)<d(v2)<…<d(vn)中至少有一個(gè)等號(hào)成立，命題成立。17三月2024結(jié)點(diǎn)的次數(shù)定義：在無向圖G=<V,E>中，若每個(gè)結(jié)點(diǎn)的度數(shù)都是k，即 (

v)(v

V

d(v)=k)，則稱G為k度正則圖(regulargraph)v1v2v6v33度正則圖v4v5v7v8v9v103度正則圖v1v5v6v2v3v417三月2024子圖三、子圖定義：給定無向圖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=

V117三月2024子圖例如：v2v1(a)v3v4v5(a)的真子圖v2v3v4v5(a)的生成子圖v2v3v4v5v117三月2024子圖定義：對(duì)于圖G=<V,E>，G1=<V,E>=G，G2=<V,

>

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

V2，若有[u,v]

E1，則有[u,v]

E2，

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

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

G2是E2的誘導(dǎo)子圖，記作G[E2]，或G2=<E2>17三月2024子圖例如：v2v1G=<V,E>v3v4v5G’=<V’,E’>

V’或E’的誘導(dǎo)子圖v2v3v4v517三月2024補(bǔ)圖定義：

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

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

則稱G2是相對(duì)于G的G1的補(bǔ)圖17三月2024補(bǔ)圖 圖G1和G2互為相對(duì)于G補(bǔ)圖G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v517三月2024補(bǔ)圖定義：

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

且E1

E2=

，及圖<V,E1

E2

>是完全圖

則稱G2是相對(duì)于完全圖的G1的補(bǔ)圖，記作G2=G117三月2024補(bǔ)圖

G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v117三月2024圖的同構(gòu)四、圖的同構(gòu)定義：

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

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

V2，使得對(duì)于任意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

G217三月2024圖的同構(gòu)例7.1.1證明下面兩個(gè)圖G1=<V1,E1>，G2=<V2,E2>同構(gòu)證明：V1={v1,v2,v3,v4},V2={a,b,c,d}構(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

G2v2v1G1v3v4badcG217三月2024圖的同構(gòu)例7.1.2證明下面兩個(gè)有向圖是同構(gòu)的。G1eabcd證明：如圖所示，G1=<V1,E1>，G2=<V2,E2>，結(jié)點(diǎn)編號(hào)如圖所示。 構(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)G13124517三月2024圖的同構(gòu)可以給出圖的同構(gòu)的必要條件：結(jié)點(diǎn)數(shù)相等邊數(shù)相等度數(shù)相等的結(jié)點(diǎn)數(shù)相等要注意的是，這不是充分條件17三月2024圖的同構(gòu)例7.1.3證明下面兩個(gè)無向圖是不同構(gòu)的G1v1v2v3v4v5v6v7v8G2abcdefghv1是3度結(jié)點(diǎn)，故f(v1)只能是c或d或g或h。若f(v1)=c，由于v2、v4和v5與v1鄰接，因此f(v2)、f(v4)和f(v5)應(yīng)當(dāng)分別為與c鄰接的b、d和g。但是，v2、v4和v5中，只有一個(gè)3度結(jié)點(diǎn)，而b、d、g中卻有2個(gè)3度結(jié)點(diǎn)，故f(v1)≠c。同理可說明，f(v1)也不可能是d、g和h。因此這樣的f是不存在的。因此G1和G2是不同構(gòu)的。17三月2024第二節(jié)路(鏈)與回路(圈)一、路(鏈)與回路(圈)定義：給定圖G=<V,E>，令v0,v1,…,vm

V，e1,e2,…,em

E稱交替序列v0e1v1

e2

v2…emvm為連接v0到vm的鏈（路）稱v0和vm為鏈（路）的始結(jié)點(diǎn)和終結(jié)點(diǎn)鏈的長(zhǎng)度為邊（?。┑臄?shù)目m若v0=vm，該鏈（路）稱為圈（回路,circuit）17三月2024鏈和圈在鏈中：若任意ei只出現(xiàn)一次，則稱該鏈（路）為簡(jiǎn)單鏈（路）若任意vi只出現(xiàn)一次，則稱該鏈（路）為基本鏈（路）基本鏈必定是簡(jiǎn)單鏈在圈中：若任意ei只出現(xiàn)一次，則稱該圈（回路）為簡(jiǎn)單圈（回路）若任意vi只出現(xiàn)一次，則稱該圈（回路）為基本圈（回路）17三月2024鏈和圈例7.2.1下圖中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1e1v2e7v5)

也可以表示為：P1=(e1e7)

是一個(gè)基本鏈，也是一個(gè)簡(jiǎn)單鏈P2=(v2e2v3e3v3e4v1e1v2)

也可以表示為：P2=(e2e3e4e1

)

是一個(gè)簡(jiǎn)單圈，但不是基本圈P3=(v4e6v2e7v5e8v4e6v2e2v3)是一個(gè)鏈P4=(v2e7v5e8v4e6v2)是一個(gè)基本圈，也是一個(gè)簡(jiǎn)單圈17三月2024鏈和圈鏈和圈可以只用邊的序列表示

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

(v4e6v2e7v5e8v4e6v2e2v3)也可表示為(e6e7e8e6e2)對(duì)于簡(jiǎn)單圖來說，鏈和圈可以僅用結(jié)點(diǎn)序列表示v3v1v4v5v2e1e2e4e5e6e3e8圖中：

(v2e2v3e4v1e1v2e3v5e8v4)

可表示為(e2e4e1e3e8)

也可表示為(v2v3v1v2v5v4)17三月2024鏈和圈定理：在一個(gè)圖中，若從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj存在一條鏈（路）， 則必有一條從vi到vj的基本鏈（路）證明：1)若從vi到vj給定的鏈本身就是基本鏈，定理成立2)若從vi到vj給定的鏈不是基本鏈，則至少含有一個(gè)結(jié)點(diǎn)vk，它在該鏈中至少出現(xiàn)兩次以上。也就是說，經(jīng)過vk有一個(gè)圈

，于是可以從原有鏈中去除

中所有出現(xiàn)的邊（弧）。對(duì)于原鏈中所含的所有圈都做此處理，最終將得到一條基本鏈（路）17三月2024鏈和圈問題：在一個(gè)圖中，若從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj存在一個(gè)圈，

則必有一個(gè)從vi到vj的基本圈嗎？例7.2.2若u和v是一個(gè)圈上的兩個(gè)結(jié)點(diǎn)，u和v一定是某個(gè)基本圈上的結(jié)點(diǎn)嗎？(習(xí)題7-16)答：不一定vaudcb本圖中，u和v在一個(gè)圈上，但是卻不在一個(gè)基本圈上17三月2024鏈和圈定理：在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，任何基本鏈（路）的長(zhǎng)度不大于n-1任何基本圈（回路）的長(zhǎng)度不大于n證明：1)根據(jù)基本鏈的定義可知，出現(xiàn)在基本鏈中的結(jié)點(diǎn)都是不同的。因此在長(zhǎng)度為m的基本鏈中，不同的結(jié)點(diǎn)數(shù)為m+1又因?yàn)閳D中僅有n個(gè)結(jié)點(diǎn)，故m+1≤n，即m≤n-12)根據(jù)基本圈的定義可知，長(zhǎng)度為k的基本圈中，不同的結(jié)點(diǎn)數(shù)為k，圖中共有n個(gè)結(jié)點(diǎn)，所以k≤n17三月2024可達(dá)二、連通圖定義：

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

則稱從vi到vj是可達(dá)的(accessible)，簡(jiǎn)稱vi可達(dá)vj規(guī)定：每個(gè)結(jié)點(diǎn)vi到自身都是可達(dá)的17三月2024連通無向圖（一）連通無向圖對(duì)于無向圖G=<V,E>而言，可證明“可達(dá)性”是一個(gè)___關(guān)系。它對(duì)V給出一個(gè)劃分，每個(gè)塊中的元素形成一個(gè)誘導(dǎo)子圖。兩個(gè)結(jié)點(diǎn)間是可達(dá)的，當(dāng)且僅當(dāng)它們屬于同一個(gè)子圖

稱這樣的子圖為G的連通分圖，G的連通分圖的個(gè)數(shù)記為

(G)若G中只有一個(gè)連通分圖，則稱G是連通圖(即任意兩結(jié)點(diǎn)可達(dá))

否則稱G為非連通圖，或分離圖等價(jià)17三月2024連通無向圖定義：在無向圖G=<V,E>中若任意兩個(gè)結(jié)點(diǎn)可達(dá)，則稱G是連通的(connected)，

稱G為連通無向圖；

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

子圖G’’是連通的，則稱G’是G的連通分圖(connectedcomponents)，簡(jiǎn)稱分圖。G中連通分圖的個(gè)數(shù)記為

(G)。17三月2024連通無向圖例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是連通圖，

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

(G2)=217三月2024連通無向圖定義：從圖G=<V,E>中刪除結(jié)點(diǎn)集S，是指V-SE-{與S中結(jié)點(diǎn)相連結(jié)的邊}而得到的子圖，記做G-SG-{v3}v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v217三月2024連通無向圖定義：從圖G=<V,E>中刪除結(jié)點(diǎn)集S，是指V-SE-{與S中結(jié)點(diǎn)相連結(jié)的邊}而得到的子圖，記做G-SG-{v3}v1v4v5v2G17三月2024連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到的子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v217三月2024連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到的子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge2e5e6e717三月2024連通無向圖定義：給定連通無向圖G=<V,E>，S

V若

(G-S)>

(G)=1且對(duì)任意T

S，

(G-T)=

(G)則稱S是G的一個(gè)分離結(jié)點(diǎn)集(cut-setofnodes)若S中僅含有一個(gè)元素v，則稱v是G的割點(diǎn)(cut-node)17三月2024連通無向圖例7.2.4 G如下圖所示，S={v1,v3}v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S

(G)=1，

(G-S)=2

(G-S)>

(G)17三月2024連通無向圖例7.2.4 G如下圖所示，S={v1,v3}v2v1v5v6v4Gv3

(G)=1，

(G-S)=2

(G-S)>

(G)

(G-{v1})=1v2v5v6v4G-{v1}v317三月2024連通無向圖例7.2.4 G如下圖所示，S={v1,v3}v2v1v5v6v4Gv3

(G)=1，

(G-S)=2

(G-S)>

(G)

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

(G-{v3})=117三月2024連通無向圖例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é)點(diǎn)集17三月2024連通無向圖例7.2.5 G如下圖所示，S={v2}v1v4v5v3Gv2

(G)=1，

(G-S)=2

(G-S)>

(G)v1v4v5v3G-Sv2是G的割點(diǎn)不存在其他的G的割點(diǎn)17三月2024連通無向圖定義：給定連通無向圖G=<V,E>，T

E若

(G-T)>

(G)=1且對(duì)任意F

T，

(G-F)=

(G)則稱T是G的一個(gè)分離邊集(cut-setofedges)若T中僅含有一個(gè)元素e，則稱e是G的割邊(cut-edge)，或橋17三月2024連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e317三月2024連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-{e1}v2e4e2e3

(G-{e1})=117三月2024連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3

(G-{e1})=1

(G-{e2})=1v1v3v4G-{e2}v2e1e4e317三月2024連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3

(G-{e1})=1

(G-{e2})=1T是G的分離邊集17三月2024連通無向圖例7.2.7 G如下圖所示，T={e1}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e2e3v1v3v4G-Tv2e2e3e1是G的割邊e2和e3都是G的割邊17三月2024連通無向圖定義：對(duì)連通的非平凡圖G=<V,E>，稱

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

為G的結(jié)點(diǎn)連通度(node-connectivity)

它表明產(chǎn)生分離圖需要?jiǎng)h去結(jié)點(diǎn)的最少數(shù)目對(duì)分離圖G而言，

(G)=0對(duì)存在割點(diǎn)的連通圖G而言，

(G)=1S

V17三月2024連通無向圖例7.2.8 求G1和G2的結(jié)點(diǎn)連通度v2v1v5v6v4G1v3

(G1)=2

(G2)=1v1v4v5v3G2v217三月2024連通無向圖定義：對(duì)連通的非平凡圖G=<V,E>，稱

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

為G的邊連通度(edge-connectivity)

它表明產(chǎn)生分離圖需要?jiǎng)h去邊的最少數(shù)目對(duì)分離圖G而言，

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

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

(Kn)=?T

En-117三月2024連通無向圖例7.2.9 求G1和G2的邊連通度

(G1)=2

(G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e317三月2024連通無向圖定理：對(duì)于任何一個(gè)無向圖G，有

(G)≤

(G)≤

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

(G)=

(G)=0，而

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

(G)≤

(G)若G是平凡圖，則

(G)=0=

(G)若G不是平凡圖，則當(dāng)刪去所有聯(lián)結(jié)一個(gè)具有最小度的結(jié)點(diǎn)的邊（除了環(huán)）后，便產(chǎn)生了一個(gè)分離圖，因此

(G)≤

(G)再證明

(G)≤

(G)

若

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

(G)=

(G)=1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v3v4G–{v1}v2e317三月2024連通無向圖若

(G)≥2，則刪去某

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

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

(G)-1條邊中的每一條邊，選取一個(gè)不同于u和v的結(jié)點(diǎn)，把這些結(jié)點(diǎn)刪去，將必須至少刪去

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

(G)≤

(G)-1<

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

(G)≤

(G)v1v3v4Gv2e1e4e2e3v1v3v4G–{v2}e2e3v1v4G–{v3}綜上所述，有

(G)≤

(G)≤

(G)17三月2024連通無向圖定理：一個(gè)連通無向圖G中的結(jié)點(diǎn)v是割點(diǎn)，充要條件是存在兩個(gè)結(jié)點(diǎn)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必定不可達(dá)，故v是G的割點(diǎn)2)必要性：若v是G的割點(diǎn)，刪去v，則子圖G-{v}中至少有兩個(gè)連通分圖G1=<V1,E1>和G2=<V2,E2>

，任取兩個(gè)結(jié)點(diǎn)

u

V1，w

V2，u和w不可達(dá)。故G中聯(lián)結(jié)u和w的每條鏈必經(jīng)過v17三月2024連通無向圖同理可以證明：定理：一個(gè)連通無向圖G中的邊e是割邊，充要條件是存在兩個(gè)結(jié)點(diǎn)u和w，使得聯(lián)結(jié)u和w的每條鏈都經(jīng)過e定理：一個(gè)連通無向圖G中的邊e是割邊，充要條件是e不包含在G的任何基本圈中證明：教材P172（定理7.8)17三月2024烏拉姆猜想（1929）左右兩張相片，捂住左邊相片的一部分，也捂住右邊相片的相應(yīng)部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分別捂住左右相片的另一個(gè)對(duì)應(yīng)部分，例如右耳，結(jié)果能看到的相片的大部分仍然一致。如此輪番地觀察各次對(duì)應(yīng)的暴露部分，都會(huì)看到相同的形象，那么誰(shuí)都會(huì)相信這兩張照片是同一個(gè)人或?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≌G217三月2024連通有向圖（二）連通有向圖對(duì)于有向圖G=<V,E>而言，結(jié)點(diǎn)間的可達(dá)性不再是等價(jià)關(guān)系，它僅僅是自反的和可傳遞的，一般不是對(duì)稱的定義：對(duì)于給定的有向圖G，要略去G中每條邊的方向，

便得到一個(gè)無向圖G’，稱G’是G的基礎(chǔ)圖17三月2024連通有向圖定義：在簡(jiǎn)單有向圖G中，若任何兩個(gè)結(jié)點(diǎn)間都是可達(dá)的，則稱G是強(qiáng)連通的若任何兩個(gè)結(jié)點(diǎn)間，至少是從一個(gè)結(jié)點(diǎn)可達(dá)另一個(gè)結(jié)點(diǎn)，則稱G是單向連通的若G的基礎(chǔ)圖是連通的，則稱G是弱連通的17三月2024連通有向圖例7.2.10判斷G1、G2和G3是強(qiáng)連通？單向連通？弱連通？G1是強(qiáng)連通的v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是單向連通的G3是弱連通的17三月2024連通有向圖由定義可知：若G是強(qiáng)連通的，則它必定是單向連通的

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

反之未必真17三月2024連通有向圖定理：有向圖G是強(qiáng)連通的，當(dāng)且僅當(dāng)G中有一回路，它至少通過每個(gè)結(jié)點(diǎn)一次證明：1)充分性：若G中存在一條回路，它至少通過每個(gè)結(jié)點(diǎn)一回，則G中任何兩個(gè)結(jié)點(diǎn)都是互相可達(dá)的，所以G是強(qiáng)連通的。2)必要性：若G是強(qiáng)連通的，則G中任何兩個(gè)結(jié)點(diǎn)都是互相可達(dá)的，因此可以做出一條回路經(jīng)過G中所有結(jié)點(diǎn)，否則，必有某結(jié)點(diǎn)v不在該回路上，v與回路上的各結(jié)點(diǎn)不可能都互相可達(dá)。與G是強(qiáng)連通的矛盾17三月2024連通有向圖定義：在簡(jiǎn)單有向圖G中具有強(qiáng)連通性質(zhì)的極大子圖，稱為強(qiáng)分圖具有單向連通性質(zhì)的極大子圖，稱為單向分圖具有弱連通性質(zhì)的極大子圖，稱為弱分圖17三月2024連通有向圖例7.2.11 求G的強(qiáng)分圖、單向分圖和弱分圖v3v2v1Gv4v5v6v3v2v1v4v5v6G的強(qiáng)分圖有：定理：簡(jiǎn)單有向圖G中的任意一個(gè)結(jié)點(diǎn)，恰位于一個(gè)強(qiáng)分圖中17三月2024連通有向圖定理：簡(jiǎn)單有向圖G中的任意一個(gè)結(jié)點(diǎn)，恰位于一個(gè)強(qiáng)分圖中證明：由強(qiáng)分圖的定義可知，G中每個(gè)結(jié)點(diǎn)位于一個(gè)強(qiáng)分圖中假設(shè)G中存在結(jié)點(diǎn)v位于兩個(gè)強(qiáng)分圖G1和G2中則由強(qiáng)分圖的定義可知，G1中的每個(gè)結(jié)點(diǎn)與v互相可達(dá)，G2中的每個(gè)結(jié)點(diǎn)也與v互相可達(dá)故G1中的每個(gè)結(jié)點(diǎn)與G2中的每個(gè)結(jié)點(diǎn)通過v，能夠互相可達(dá)，這與G1和G2是兩個(gè)強(qiáng)分圖矛盾因此G中每個(gè)結(jié)點(diǎn)只能位于一個(gè)強(qiáng)分圖中17三月2024連通有向圖例7.2.11 求G的強(qiáng)分圖、單向分圖和弱分圖G的單向分圖有：v3v2v1Gv4v5v6v3v2v1v4v5v5v6定理：簡(jiǎn)單有向圖G中的每個(gè)結(jié)點(diǎn)和每條弧,至少位于一個(gè)單向分圖中17三月2024連通有向圖例7.2.11 求G的強(qiáng)分圖、單向分圖和弱分圖G的弱分圖有：v3v2v1Gv4v5v6v3v2v1v4v5v6定理：簡(jiǎn)單有向圖G中的每個(gè)結(jié)點(diǎn)和每條弧

恰位于一個(gè)弱分圖中17三月2024結(jié)點(diǎn)間的距離三、結(jié)點(diǎn)間的距離定義：在圖G中，若結(jié)點(diǎn)u可達(dá)結(jié)點(diǎn)v，它們之間可能存在不止一條鏈（路）。

在所有鏈中，最短鏈的長(zhǎng)度稱為結(jié)點(diǎn)u和v之間的距離

（或短程線、測(cè)地線）。記做：d<u,v>17三月2024結(jié)點(diǎn)間的距離距離滿足下面性質(zhì)：d<u,v>≥0d<u,u>=0d<u,v>+d<v,w>≥d<u,w>若u不可達(dá)v，則d<u,v>=+

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

17三月2024有向圖在計(jì)算機(jī)中的應(yīng)用四、有向圖在計(jì)算機(jī)中的應(yīng)用這里給出一個(gè)簡(jiǎn)單有向圖在計(jì)算機(jī)中的應(yīng)用——

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

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

G中包含多于一個(gè)結(jié)點(diǎn)的強(qiáng)分圖17三月2024有向圖在計(jì)算機(jī)中的應(yīng)用t時(shí)刻系統(tǒng)處于死鎖狀態(tài)

G中包含多于一個(gè)結(jié)點(diǎn)的強(qiáng)分圖解決辦法：

使G中的每個(gè)強(qiáng)分圖中

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

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

0 vinadjvj17三月2024鄰接矩陣?yán)?.3.1圖G=<V,E>如圖所示v4v5v3v2v10111110100110101010110010AG=G的鄰接矩陣為：0100110101010110010111110AG’=G’的鄰接矩陣變?yōu)椋簐3v4v2v1v5若G’中結(jié)點(diǎn)編序如下圖所示17三月2024鄰接矩陣?yán)?.3.2圖G=<V,E>如圖所示0101001010010100AG=G的鄰接矩陣為：v1v3v4v2若G’中結(jié)點(diǎn)編序如下圖所示v4v3v1v20100001010011100AG’=G’的鄰接矩陣變?yōu)椋?7三月2024鄰接矩陣對(duì)于僅僅結(jié)點(diǎn)編序不同的圖，是同構(gòu)的

它們的鄰接矩陣也是相似的G1

G2

存在置換矩陣P，使得

AG2=P-1AG1P對(duì)于由結(jié)點(diǎn)編序不同引起的鄰接矩陣的不同將被忽略

任取圖的任意一個(gè)鄰接矩陣作為該圖的矩陣表示17三月2024鄰接矩陣圖G的鄰接矩陣AG可以展示圖G的一些性質(zhì)：若鄰接矩陣AG的元素全是零，則G是若鄰接矩陣AG的元素主對(duì)角線上全是0，其他元素全是1，

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

定的，故第i行元素為1的數(shù)目，等于vi的，即d+(vi)=

aik

第j列元素是由到達(dá)結(jié)點(diǎn)vj的弧所確定的，故第j列元素為1的數(shù)目，

等于vj的，即d-(vj)=

akjn

k=1n

k=1零圖連通的簡(jiǎn)單完全圖對(duì)稱矩陣出度入度17三月2024鄰接矩陣定理：設(shè)A為簡(jiǎn)單圖G的鄰接矩陣，則An中的i行j列的元素

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

airk×

arj

根據(jù)假設(shè)可知，airk為G中聯(lián)結(jié)vi和vr的長(zhǎng)度為k的鏈的數(shù)目，arj為G中聯(lián)結(jié)vr和vj的長(zhǎng)度為1的鏈的數(shù)目，因此aijk+1為G中聯(lián)結(jié)vi和vj的長(zhǎng)度為k+1的鏈的數(shù)目17三月2024鄰接矩陣?yán)?.3.3圖G=<V,E>如圖所示，求A,A2,A3,A40101001010010100A=v1v3v4v20110100102010010A2=1011020101201001A3=1202012020120201A4=17三月2024鄰接矩陣由上面的定理可知：

若要判斷圖G中結(jié)點(diǎn)vi到vj是否可達(dá)，可以利用G的鄰接矩陣A，

計(jì)算A,A2,A3,…,An,…

若發(fā)現(xiàn)某個(gè)Ar（r是正整數(shù)）中aijr

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

對(duì)于含有n個(gè)結(jié)點(diǎn)的圖G，任何基本鏈（路）的長(zhǎng)度不大于，

任何基本圈（回路）的長(zhǎng)度不大于因此，僅考慮aijr（1≤r≤n）即可n-1n17三月2024鄰接矩陣因此，只要計(jì)算Bn=(bij)=A+A2+A3+…+An

Bn

中元素bij表示vi到vj的長(zhǎng)度小于等于n的不同路徑的總數(shù)bij≠

0時(shí)，vi可達(dá)vj；

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

0時(shí)，vi不可達(dá)vj；

若i=j，則說明不存在經(jīng)過vi的回路17三月2024鄰接矩陣?yán)?.3.4圖G=<V,E>如圖所示，求Bnv1v3v4v2Bn=A+A2+A3+A40110100102010010+1011020101201001+1202012020120201+0101001010010100=2424133233341312=17三月2024鄰接矩陣問題：如何判斷某無向圖G是否為連通圖？求出Bn=(bij)=A+A2+A3+…+An若有某個(gè)bij為0(i≠j)，則說明結(jié)點(diǎn)vi和vj處于不同的連通分圖中，圖G為分離圖；

否則G為連通圖（即非主對(duì)角線上元素都不為0）。思考：主對(duì)角線上元素bii表示什么？17三月2024可達(dá)矩陣若關(guān)心的只是結(jié)點(diǎn)間的可達(dá)性或結(jié)點(diǎn)間是否有鏈存在

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

則可以使用可達(dá)矩陣P=(pij)來表示結(jié)點(diǎn)間的可達(dá)性：pij= 1, vi

可達(dá)vj

0, vi

不可達(dá)vj17三月2024可達(dá)矩陣可達(dá)矩陣P=(pij)的計(jì)算之一：通過Bn

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

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

pij= 1, bij≠

0

0, bij＝

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

結(jié)點(diǎn)vi的圈，并不描述結(jié)點(diǎn)到自身的可達(dá)性。17三月2024可達(dá)矩陣?yán)?.3.5圖G=<V,E>如圖所示，求可達(dá)矩陣Pv1v3v4v2Bn=A+A2+A3+A42424133233341312=1111111111111111P=由P可知：G中任意兩個(gè)結(jié)點(diǎn)彼此可達(dá)任意結(jié)點(diǎn)處都有圈存在

G是強(qiáng)連通圖17三月2024可達(dá)矩陣如何判定有向圖G是否為強(qiáng)連通圖？強(qiáng)連通圖G的可達(dá)矩陣P中所有元素aij都為1（aii是否必然為1？）如何判定有向圖G是否為單向連通圖？若P∨PT中非主對(duì)角線上元素都為1，則G是單向連通圖

（主對(duì)角線上元素aii是否必然為1？）如何判定有向圖G是否為弱連通圖？根據(jù)