離散數學-圖論基礎

第七章圖論基礎

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

頂點(vertex)E——有限集合（可以為空），E中的元素稱為邊(edge)Φ——從E到V的有序對或無序對的關聯映射(associativemapping)v1v2v3(a)v1v2v3(b)v1v2v3(c)12一月2024圖的基本概念圖G=<V,E,Φ>中的每條邊都與圖中的無序對或有序對聯系若邊e

E與無序對結點[va,vb]相聯系，即Φ(e)=[va,vb]

（va,vb

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

E與有序對結點<va,vb>相聯系，即Φ(e)=<va,vb>

（va,vb

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

va是e的起始結點，vb是e的終結點v1v2v3(a)v1v2v3(b)v1v2v3(c)12一月2024圖的基本概念若va和vb與邊（?。〆相聯結，則稱va和vb是e的端結點

va和vb是鄰接結點，記作：va

adjvb

(adjoin)

也稱e關聯va和vb，或稱va和vb關聯e若va和vb不與任何邊（?。┫嗦摻Y，則稱va和vb是非鄰接結點，記作：va

nadjvb關聯同一個結點的兩條邊（弧），稱為鄰接邊（弧）關聯同一個結點及其自身的邊，稱為環(huán)(cycle)，環(huán)的方向沒有意義v1v2v3(a)v1v2v3(b)v1v2v3(c)12一月2024圖的基本概念若將圖G中的每條邊（弧）都看作聯結兩個結點

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

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

（如圖a）

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

兩個結點間的多條邊（同向?。┓Q為平行邊（弧），

平行邊（弧）的條數，稱為重數v1v2v3(a)v1v2v3(b)v1v2v3(c)12一月2024圖的基本概念在多重圖的表示中，可在邊（?。┥蠘俗⒄麛担员硎酒叫羞叄ɑ。┑闹財蛋阎財底鳛榉峙浣o邊（?。┥系臄担Q為權(weight)

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

記作G=<V,E,W>，W是各邊權之和v1v2v3(a)v1v2v3(b)v1v2v3(c)111111221112一月2024圖的基本概念在無向圖G=<V,E>中，V中的每個結點都與其余的所有結點鄰接，即 (

va)(

vb)(va,vb

V

[va,vb]

E)，如圖(a)

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

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

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

(

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)2n12一月2024圖的基本概念在圖G=<V,E>中，若有一個結點不與其他任何結點鄰接

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

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

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

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

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

（次數），記為d(v)=d+(v)+d-(v)v1v2v3(a)12一月2024結點的次數定義：在無向圖G=<V,E>中，對任意結點v

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

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

V}

記G的最小度數為：

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

V}v1v2v3(a)v1v2v3(b)v412一月2024結點的次數在圖G中的任意一條邊e

E，都對其聯結的結點貢獻度數2定理：在無向圖G=<V,E>中，

d(v)

=2|E|通常，將度數為奇數的結點稱為奇度結點

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

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

邊通常表示兩個結點間的關系——表示2個人意見一致。

也就是說，意見一致的2個人（結點）間存在一條邊。12一月2024結點的次數問題1：是否存在這種情況：25個人中，由于意見不同，每個人恰好與其他5個人意見一致？這樣我們可以知道，如果存在題目所述情況，那么每個結點都與其他5個結點相關聯。

也就是說，每個結點的度為5。由定理可知：奇度結點的個數為偶數個。

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

0≤

d(v1)<d(v2)<…<d(vn)≤n-1。12一月2024結點的次數問題2：是否存在這種情況：兩個人或以上的人群中，至少有兩個人在此人群中的朋友數一樣多？若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，則每個結點皆與vn相鄰，則d(v1)≥1。于是有：d(v2)≥2，d(v3)≥3，…，d(vn)≥n，矛盾。故假設不成立，即d(v1)<d(v2)<…<d(vn)中至少有一個等號成立，命題成立。12一月2024結點的次數定義：在無向圖G=<V,E>中，若每個結點的度數都是k，即 (

v)(v

V

d(v)=k)，則稱G為k度正則圖(regulargraph)v1v2v6v33度正則圖v4v5v7v8v9v103度正則圖v1v5v6v2v3v412一月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=

V112一月2024子圖例如：v2v1(a)v3v4v5(a)的真子圖v2v3v4v5(a)的生成子圖v2v3v4v5v112一月2024子圖定義：對于圖G=<V,E>，G1=<V,E>=G，G2=<V,

>

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

V2，若有[u,v]

E1，則有[u,v]

E2，

則G2由V2唯一地確定，則稱G2是V2的誘導子圖

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

G2是E2的誘導子圖，記作G[E2]，或G2=<E2>12一月2024子圖例如：v2v1G=<V,E>v3v4v5G’=<V’,E’>

V’或E’的誘導子圖v2v3v4v512一月2024補圖定義：

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

若E2=E-E1，且G2是E2的誘導子圖，即G2=<E2>

則稱G2是相對于G的G1的補圖12一月2024補圖 圖G1和G2互為相對于G補圖G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v512一月2024補圖定義：

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

且E1

E2=

，及圖<V,E1

E2

>是完全圖

則稱G2是相對于完全圖的G1的補圖，記作G2=G112一月2024補圖

G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v112一月2024圖的同構四、圖的同構定義：

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

若存在雙射函數f:V1

V2，使得對于任意u,v

V1

有 [u,v]

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

E2

（或<u,v>

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

E2）

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

G212一月2024圖的同構例7.1.1證明下面兩個圖G1=<V1,E1>，G2=<V2,E2>同構證明：V1={v1,v2,v3,v4},V2={a,b,c,d}構造雙射函數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

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

V，e1,e2,…,em

E稱交替序列v0e1v1e2v2…emvm為連接v0到vm的鏈（路）稱v0和vm為鏈（路）的始結點和終結點鏈的長度為邊（?。┑臄的縨若v0=vm，該鏈（路）稱為圈（回路,circuit）12一月2024鏈和圈在鏈中：若任意ei只出現一次，則稱該鏈（路）為簡單鏈（路）若任意vi只出現一次，則稱該鏈（路）為基本鏈（路）基本鏈必定是簡單鏈在圈中：若任意ei只出現一次，則稱該圈（回路）為簡單圈（回路）若任意vi只出現一次，則稱該圈（回路）為基本圈（回路）12一月2024鏈和圈例7.2.1下圖中：v3v1v4v5v2e1e2e3e4e5e6e7e8P1=(v1e1v2e7v5)

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

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

也可以表示為：P2=(e2e3e4e1

)

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

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

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

(v2e2v3e4v1e1v2e3v5e8v4)

可表示為(e2e4e1e3e8)

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

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

中所有出現的邊（?。?。對于原鏈中所含的所有圈都做此處理，最終將得到一條基本鏈（路）12一月2024鏈和圈問題：在一個圖中，若從結點vi到結點vj存在一個圈，

則必有一個從vi到vj的基本圈嗎？例7.2.2若u和v是一個圈上的兩個結點，u和v一定是某個基本圈上的結點嗎？(習題7-16)答：不一定vaudcb本圖中，u和v在一個圈上，但是卻不在一個基本圈上12一月2024鏈和圈定理：在一個具有n個結點的圖中，任何基本鏈（路）的長度不大于n-1任何基本圈（回路）的長度不大于n證明：1)根據基本鏈的定義可知，出現在基本鏈中的結點都是不同的。因此在長度為m的基本鏈中，不同的結點數為m+1又因為圖中僅有n個結點，故m+1≤n，即m≤n-12)根據基本圈的定義可知，長度為k的基本圈中，不同的結點數為k，圖中共有n個結點，所以k≤n12一月2024可達二、連通圖定義：

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

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

稱這樣的子圖為G的連通分圖，G的連通分圖的個數記為

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

否則稱G為非連通圖，或分離圖等價12一月2024連通無向圖定義：在無向圖G=<V,E>中若任意兩個結點可達，則稱G是連通的(connected)，

稱G為連通無向圖；

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

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

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

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

(G2)=212一月2024連通無向圖定義：從圖G=<V,E>中刪除結點集S，是指V-SE-{與S中結點相連結的邊}而得到的子圖，記做G-SG-{v3}v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v212一月2024連通無向圖定義：從圖G=<V,E>中刪除結點集S，是指V-SE-{與S中結點相連結的邊}而得到的子圖，記做G-SG-{v3}v1v4v5v2G12一月2024連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到的子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v212一月2024連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到的子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge2e5e6e712一月2024連通無向圖定義：給定連通無向圖G=<V,E>，S

V若

(G-S)>

(G)=1且對任意T

S，

(G-T)=

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

(G)=1，

(G-S)=2

(G-S)>

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

(G)=1，

(G-S)=2

(G-S)>

(G)

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

(G)=1，

(G-S)=2

(G-S)>

(G)

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

(G-{v3})=112一月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的分離結點集12一月2024連通無向圖例7.2.5 G如下圖所示，S={v2}v1v4v5v3Gv2

(G)=1，

(G-S)=2

(G-S)>

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

E若

(G-T)>

(G)=1且對任意F

T，

(G-F)=

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

(G)=1，

(G-T)=2

(G-T)>

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

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-{e1}v2e4e2e3

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

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3

(G-{e1})=1

(G-{e2})=1v1v3v4G-{e2}v2e1e4e312一月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的分離邊集12一月2024連通無向圖例7.2.7 G如下圖所示，T={e1}

(G)=1，

(G-T)=2

(G-T)>

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

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

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

它表明產生分離圖需要刪去結點的最少數目對分離圖G而言，

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

(G)=1S

V12一月2024連通無向圖例7.2.8 求G1和G2的結點連通度v2v1v5v6v4G1v3

(G1)=2

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

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

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

它表明產生分離圖需要刪去邊的最少數目對分離圖G而言，

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

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

(Kn)=?T

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

(G1)=2

(G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e312一月2024連通無向圖定理：對于任何一個無向圖G，有

(G)≤

(G)≤

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

(G)=

(G)=0，而

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

(G)≤

(G)若G是平凡圖，則

(G)=0=

(G)若G不是平凡圖，則當刪去所有聯結一個具有最小度的結點的邊（除了環(huán)）后，便產生了一個分離圖，因此

(G)≤

(G)再證明

(G)≤

(G)

若

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

(G)=

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

(G)≥2，則刪去某

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

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

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

(G)-1條邊若這樣會產生分離圖，則

(G)≤

(G)-1<

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

(G)≤

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

(G)≤

(G)≤

(G)12一月2024連通無向圖定理：一個連通無向圖G中的結點v是割點，充要條件是存在兩個結點u和w，使得聯結u和w的每條鏈都經過v證明：1)充分性：若G中聯結u和w的每條鏈都經過v，刪去v，則在子圖G-{v}中，u和w必定不可達，故v是G的割點2)必要性：若v是G的割點，刪去v，則子圖G-{v}中至少有兩個連通分圖G1=<V1,E1>和G2=<V2,E2>

，任取兩個結點

u

V1，w

V2，u和w不可達。故G中聯結u和w的每條鏈必經過v12一月2024連通無向圖同理可以證明：定理：一個連通無向圖G中的邊e是割邊，充要條件是存在兩個結點u和w，使得聯結u和w的每條鏈都經過e定理：一個連通無向圖G中的邊e是割邊，充要條件是e不包含在G的任何基本圈中證明：教材P172（定理7.8)12一月2024烏拉姆猜想（1929）左右兩張相片，捂住左邊相片的一部分，也捂住右邊相片的相應部分，例如都捂住左眼，能看到的相片的大部分形象一致；再分別捂住左右相片的另一個對應部分，例如右耳，結果能看到的相片的大部分仍然一致。如此輪番地觀察各次對應的暴露部分，都會看到相同的形象，那么誰都會相信這兩張照片是同一個人或孿生兄弟的留影。數學描述：有圖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≌G212一月2024連通有向圖（二）連通有向圖對于有向圖G=<V,E>而言，結點間的可達性不再是等價關系，它僅僅是自反的和可傳遞的，一般不是對稱的定義：對于給定的有向圖G，要略去G中每條邊的方向，

便得到一個無向圖G’，稱G’是G的基礎圖12一月2024連通有向圖定義：在簡單有向圖G中，若任何兩個結點間都是可達的，則稱G是強連通的若任何兩個結點間，至少是從一個結點可達另一個結點，則稱G是單向連通的若G的基礎圖是連通的，則稱G是弱連通的12一月2024連通有向圖例7.2.10判斷G1、G2和G3是強連通？單向連通？弱連通？G1是強連通的v1v3v4G1v2v1v3v4G2v2v1v3v4G3v2G2是單向連通的G3是弱連通的12一月2024連通有向圖由定義可知：若G是強連通的，則它必定是單向連通的

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

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

恰位于一個弱分圖中12一月2024結點間的距離三、結點間的距離定義：在圖G中，若結點u可達結點v，它們之間可能存在不止一條鏈（路）。

在所有鏈中，最短鏈的長度稱為結點u和v之間的距離

（或短程線、測地線）。記做：d<u,v>12一月2024結點間的距離距離滿足下面性質：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>12一月2024有向圖在計算機中的應用四、有向圖在計算機中的應用這里給出一個簡單有向圖在計算機中的應用——

利用資源分配圖來糾正和發(fā)現死鎖12一月2024有向圖在計算機中的應用在多道程序的計算機系統(tǒng)中，同一時間內有多個程序需要同時執(zhí)行。每個程序都共享計算機資源：如CPU、內存、外存、輸入設備、編譯系統(tǒng)等，操作系統(tǒng)將對這些資源分配給各個程序。當一個程序需要使用某種資源的時候，要向操作系統(tǒng)發(fā)出請求，操作系統(tǒng)必須保證這個請求得到滿足，才能運行該程序12一月2024有向圖在計算機中的應用對資源的請求可能發(fā)生沖突，發(fā)生死鎖。例如：程序P1占有資源r1，請求資源r2程序P2占有資源r2，請求資源r1有沖突的請求必須要解決，可以利用有向圖來模擬對資源的請求，從而幫助發(fā)現和糾正“死鎖”狀態(tài)12一月2024有向圖在計算機中的應用令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中包含多于一個結點的強分圖12一月2024有向圖在計算機中的應用t時刻系統(tǒng)處于死鎖狀態(tài)

G中包含多于一個結點的強分圖解決辦法：

使G中的每個強分圖中

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

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

0 vinadjvj12一月2024鄰接矩陣例7.3.1圖G=<V,E>如圖所示v4v5v3v2v10111110100110101010110010AG=G的鄰接矩陣為：0100110101010110010111110AG’=G’的鄰接矩陣變?yōu)椋簐3v4v2v1v5若G’中結點編序如下圖所示12一月2024鄰接矩陣例7.3.2圖G=<V,E>如圖所示0101001010010100AG=G的鄰接矩陣為：v1v3v4v2若G’中結點編序如下圖所示v4v3v1v20100001010011100AG’=G’的鄰接矩陣變?yōu)椋?2一月2024鄰接矩陣對于僅僅結點編序不同的圖，是同構的

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

G2

存在置換矩陣P，使得

AG2=P-1AG1P對于由結點編序不同引起的鄰接矩陣的不同將被忽略

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

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

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

aik

第j列元素是由到達結點vj的弧所確定的，故第j列元素為1的數目，

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

akjn

k=1n

k=1零圖連通的簡單完全圖對稱矩陣出度入度12一月2024鄰接矩陣定理：設A為簡單圖G的鄰接矩陣，則An中的i行j列的元素

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

airk×

arj

根據假設可知，airk為G中聯結vi和vr的長度為k的鏈的數目，arj為G中聯結vr和vj的長度為1的鏈的數目，因此aijk+1為G中聯結vi和vj的長度為k+1的鏈的數目12一月2024鄰接矩陣例7.3.3圖G=<V,E>如圖所示，求A,A2,A3,A40101001010010100A=v1v3v4v20110100102010010A2=1011020101201001A3=1202012020120201A4=12一月2024鄰接矩陣由上面的定理可知：

若要判斷圖G中結點vi到vj是否可達，可以利用G的鄰接矩陣A，

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

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

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

對于含有n個結點的圖G，任何基本鏈（路）的長度不大于，

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

Bn

中元素bij表示vi到vj的長度小于等于n的不同路徑的總數bij≠

0時，vi可達vj；

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

0時，vi不可達vj；

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

否則G為連通圖（即非主對角線上元素都不為0）。思考：主對角線上元素bii表示什么？12一月2024可達矩陣若關心的只是結點間的可達性或結點間是否有鏈存在

至于存在多少條鏈以及長度為多少無關緊要

則可以使用可達矩陣P=(pij)來表示結點間的可達性：pij= 1, vi

可達vj

0, vi

不可達vj12一月2024可達矩陣可達矩陣P=(pij)的計算之一：通過Bn

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

再將Bn中非零元素改為1，零元素不變，即可得到Ppij= 1, bij≠

0

0, bij＝

0注意：可達矩陣中，主對角線元素aii只表現了是否存在經過

結點vi的圈，并不描述結點到自身的可達性。12一月2024可達矩陣例7.3.5圖G=<V,E>如圖所示，求可達矩陣Pv1v3v4v2Bn=A+A2+A3+A42424133233341312=1111111111111111P=由P可知：G中任意兩個結點彼此可達任意結點處都有圈存在

G是強連通圖12一月2024可達矩陣如何判定有向圖G是否為強連通圖？強連通圖G的可達矩陣P中所有元素aij都為1（aii是否必然為1？）如何判定有向圖G是否為單向連通圖？若P∨PT中非主對角線上元素都為1，則G是單向連通圖

（主對角線上元素aii是否必然為1？）如何判定有向