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

章圖論基礎(chǔ)

Graphs

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

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

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

（va,vb

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

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

（va,vb

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

va是e的起始結(jié)點，vb是e的終結(jié)點v1v2v3(a)v1v2v3(b)v1v2v3(c)2021/6/27圖的基本概念若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é)點的兩條邊（?。?，稱為鄰接邊（?。╆P(guān)聯(lián)同一個結(jié)點及其自身的邊，稱為環(huán)(cycle)，環(huán)的方向沒有意義v1v2v3(a)v1v2v3(b)v1v2v3(c)2021/6/27圖的基本概念若將圖G中的每條邊（?。┒伎醋髀?lián)結(jié)兩個結(jié)點

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

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

（如圖a）

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

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

平行邊（弧）的條數(shù)，稱為重數(shù)v1v2v3(a)v1v2v3(b)v1v2v3(c)2021/6/27圖的基本概念在多重圖的表示中，可在邊（?。┥蠘?biāo)注正整數(shù)，以表示平行邊（?。┑闹財?shù)把重數(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)11111122112021/6/27圖的基本概念在無向圖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)2n2021/6/27圖的基本概念在有向圖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)2n2021/6/27圖的基本概念在圖G=<V,E>中，若有一個結(jié)點不與其他任何結(jié)點鄰接

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

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

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

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

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

（次數(shù)），記為d(v)=d+(v)+d-(v)v1v2v3(a)2021/6/27結(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)v42021/6/27結(jié)點的次數(shù)在圖G中的任意一條邊e

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

d(v)

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

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

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

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

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

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

現(xiàn)在是否能夠得出結(jié)論了？2021/6/27結(jié)點的次數(shù)類似問題：晚會上大家握手言歡，握過奇數(shù)次手的人數(shù)一定是偶數(shù)碳?xì)浠衔镏?，氫原子個數(shù)是偶數(shù)是否有這樣的多面體，它有奇數(shù)個面，每個面有奇數(shù)條棱？2021/6/27結(jié)點的次數(shù)問題2：是否存在這種情況：兩個人或以上的人群中，至少有兩個人在此人群中的朋友數(shù)一樣多？以人為結(jié)點，僅當(dāng)二人為朋友時，在此二人之間連一邊，得一“友誼圖”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。2021/6/27結(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)中至少有一個等號成立，命題成立。2021/6/27結(jié)點的次數(shù)定義：在無向圖G=<V,E>中，若每個結(jié)點的度數(shù)都是k，即 (

v)(v

V

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

V12021/6/27子圖例如：v2v1(a)v3v4v5(a)的真子圖v2v3v4v5(a)的生成子圖v2v3v4v5v12021/6/27子圖定義：對于圖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>2021/6/27子圖例如：v2v1G=<V,E>v3v4v5G’=<V’,E’>

V’或E’的誘導(dǎo)子圖v2v3v4v52021/6/27補(bǔ)圖定義：

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

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

則稱G2是相對于G的G1的補(bǔ)圖2021/6/27補(bǔ)圖 圖G1和G2互為相對于G補(bǔ)圖G1v2v1v3v4v5G2v2v3v4v5Gv2v1v3v4v52021/6/27補(bǔ)圖定義：

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

且E1

E2=

，及圖<V,E1

E2

>是完全圖

則稱G2是相對于完全圖的G1的補(bǔ)圖，記作G2=G12021/6/27補(bǔ)圖

G2=G1v2v1G1v3v4v5v2v1K5v3v4v5G2v2v3v4v5v12021/6/27圖的同構(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

G22021/6/27圖的同構(gòu)例7.1.1證明下面兩個圖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

G2v2v1G1v3v4badcG22021/6/27圖的同構(gòu)例7.1.2證明下面兩個有向圖是同構(gòu)的。G1eabcd證明：如圖所示，G1=<V1,E1>，G2=<V2,E2>，結(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)G1312452021/6/27圖的同構(gòu)可以給出圖的同構(gòu)的必要條件：結(jié)點數(shù)相等邊數(shù)相等度數(shù)相等的結(jié)點數(shù)相等要注意的是，這不是充分條件2021/6/27圖的同構(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)當(dā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)的。2021/6/27第二節(jié)路(鏈)與回路(圈)一、路(鏈)與回路(圈)定義：給定圖G=<V,E>，令v0,v1,…,vm

V，e1,e2,…,em

E稱交替序列v0e1v1

e2

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

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

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

也可以表示為：P2=(e2e3e4e1

)

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

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

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

(v2e2v3e4v1e1v2e3v5e8v4)

可表示為(e2e4e1e3e8)

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

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

中所有出現(xiàn)的邊（?。τ谠溨兴乃腥Χ甲龃颂幚?，最終將得到一條基本鏈（路）2021/6/27鏈和圈問題：在一個圖中，若從結(jié)點vi到結(jié)點vj存在一個圈，

則必有一個從vi到vj的基本圈嗎？例7.2.2若u和v是一個圈上的兩個結(jié)點，u和v一定是某個基本圈上的結(jié)點嗎？(習(xí)題7-16)答：不一定vaudcb本圖中，u和v在一個圈上，但是卻不在一個基本圈上2021/6/27鏈和圈定理：在一個具有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≤n2021/6/27可達(dá)二、連通圖定義：

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

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

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

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

否則稱G為非連通圖，或分離圖等價2021/6/27連通無向圖定義：在無向圖G=<V,E>中若任意兩個結(jié)點可達(dá)，則稱G是連通的(connected)，

稱G為連通無向圖；

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

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

(G)。2021/6/27連通無向圖例7.2.3v3v1v4v5v2v3v1v4v5v2G1G2G1是連通圖，

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

(G2)=22021/6/27連通無向圖定義：從圖G=<V,E>中刪除結(jié)點集S，是指V-SE-{與S中結(jié)點相連結(jié)的邊}而得到的子圖，記做G-SG-{v3}v3v1v4v5v2Gv3v1v4v5v2v3v1v4v5v22021/6/27連通無向圖定義：從圖G=<V,E>中刪除結(jié)點集S，是指V-SE-{與S中結(jié)點相連結(jié)的邊}而得到的子圖，記做G-SG-{v3}v1v4v5v2G2021/6/27連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到的子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge1e2e3e4e5e6e7v3v1v4v5v22021/6/27連通無向圖定義：從圖G=<V,E>中刪除邊集T，是指V不變E-T而得到的子圖，記做G-TG-{e1,e3,e4}v3v1v4v5v2Ge2e5e6e72021/6/27連通無向圖定義：給定連通無向圖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)2021/6/27連通無向圖例7.2.4 G如下圖所示，S={v1,v3}v2v1v5v6v4Gv3v2v1v5v6v4G-Sv3v2v5v6v4G-S

(G)=1，

(G-S)=2

(G-S)>

(G)2021/6/27連通無向圖例7.2.4 G如下圖所示，S={v1,v3}v2v1v5v6v4Gv3

(G)=1，

(G-S)=2

(G-S)>

(G)

(G-{v1})=1v2v5v6v4G-{v1}v32021/6/27連通無向圖例7.2.4 G如下圖所示，S={v1,v3}v2v1v5v6v4Gv3

(G)=1，

(G-S)=2

(G-S)>

(G)

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

(G-{v3})=12021/6/27連通無向圖例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é)點集2021/6/27連通無向圖例7.2.5 G如下圖所示，S={v2}v1v4v5v3Gv2

(G)=1，

(G-S)=2

(G-S)>

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

E若

(G-T)>

(G)=1且對任意F

T，

(G-F)=

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

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e32021/6/27連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-{e1}v2e4e2e3

(G-{e1})=12021/6/27連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3

(G-{e1})=1

(G-{e2})=1v1v3v4G-{e2}v2e1e4e32021/6/27連通無向圖例7.2.6 G如下圖所示，T={e1,e2}

(G)=1，

(G-T)=2

(G-T)>

(G)v1v3v4Gv2e1e4e2e3v1v3v4G-Tv2e4e3

(G-{e1})=1

(G-{e2})=1T是G的分離邊集2021/6/27連通無向圖例7.2.7 G如下圖所示，T={e1}

(G)=1，

(G-T)=2

(G-T)>

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

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

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

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

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

(G)=1S

V2021/6/27連通無向圖例7.2.8 求G1和G2的結(jié)點連通度v2v1v5v6v4G1v3

(G1)=2

(G2)=1v1v4v5v3G2v22021/6/27連通無向圖定義：對連通的非平凡圖G=<V,E>，稱

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

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

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

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

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

(Kn)=?T

En-12021/6/27連通無向圖例7.2.9 求G1和G2的邊連通度

(G1)=2

(G2)=1v1v3v4G1v2e1e4e2e3v1v3v4G2v2e1e2e32021/6/27連通無向圖定理：對于任何一個無向圖G，有

(G)≤

(G)≤

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

(G)=

(G)=0，而

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

(G)≤

(G)若G是平凡圖，則

(G)=0=

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

(G)≤

(G)再證明

(G)≤

(G)

若

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

(G)=

(G)=1v3v1v4v5v2v1v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v1v3v4Gv2e1e2e3v1v3v4G–{e1}v2e2e3v3v4G–{v1}v2e32021/6/27連通無向圖若

(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)2021/6/27連通無向圖定理：一個連通無向圖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必定不可達(dá)，故v是G的割點2)必要性：若v是G的割點，刪去v，則子圖G-{v}中至少有兩個連通分圖G1=<V1,E1>和G2=<V2,E2>

，任取兩個結(jié)點

u

V1，w

V2，u和w不可達(dá)。故G中聯(lián)結(jié)u和w的每條鏈必經(jīng)過v2021/6/27連通無向圖同理可以證明：定理：一個連通無向圖G中的邊e是割邊，充要條件是存在兩個結(jié)點u和w，使得聯(lián)結(jié)u和w的每條鏈都經(jīng)過e定理：一個連通無向圖G中的邊e是割邊，充要條件是e不包含在G的任何基本圈中證明：教材P172（定理7.8)2021/6/27烏拉姆猜想（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≌G22021/6/27連通有向圖（二）連通有向圖對于有向圖G=<V,E>而言，結(jié)點間的可達(dá)性不再是等價關(guān)系，它僅僅是自反的和可傳遞的，一般不是對稱的定義：對于給定的有向圖G，要略去G中每條邊的方向，

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

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

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

恰位于一個弱分圖中2021/6/27結(jié)點間的距離三、結(jié)點間的距離定義：在圖G中，若結(jié)點u可達(dá)結(jié)點v，它們之間可能存在不止一條鏈（路）。

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

（或短程線、測地線）。記做：d<u,v>2021/6/27結(jié)點間的距離距離滿足下面性質(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>

2021/6/27有向圖在計算機(jī)中的應(yīng)用四、有向圖在計算機(jī)中的應(yīng)用這里給出一個簡單有向圖在計算機(jī)中的應(yīng)用——

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

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

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

都是單個結(jié)點r4r3r2r1P1P3P2P2P4P4r4r3r2r1P1P3P2P22021/6/2704一月20253x+1猜想（卡拉茲）20世紀(jì)30年代，漢堡大學(xué)的卡拉茲（Callatz）提出一個猜想：x0是一個自然數(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ī)檢驗了所有不超過240≈1.2×1012的自然數(shù)，結(jié)果都符合卡拉茲的猜想。2021/6/2704一月20253x+1猜想（卡拉茲）如果把一批自然數(shù)放在最高層，用3x+1問題的規(guī)則算出第二層的值，繼而算出第三層的值……。圖中的結(jié)點是自然數(shù)，當(dāng)數(shù)1算出數(shù)2時，則在圖上畫上有向邊<數(shù)1,數(shù)2>，得到的有向圖稱為卡拉茲有向圖，如圖所示。3x+1猜想中，卡拉茲圖的最底層結(jié)點是1。2021/6/27第三節(jié)圖的矩陣表示一、圖的矩陣表示定義：給定簡單圖G=<V,E>，V={v1,v2,…,vn}

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

0 vinadjvj2021/6/27鄰接矩陣?yán)?.3.1圖G=<V,E>如圖所示v4v5v3v2v10111110100110101010110010AG=G的鄰接矩陣為：0100110101010110010111110AG’=G’的鄰接矩陣變?yōu)椋簐3v4v2v1v5若G’中結(jié)點編序如下圖所示2021/6/27鄰接矩陣?yán)?.3.2圖G=<V,E>如圖所示0101001010010100AG=G的鄰接矩陣為：v1v3v4v2若G’中結(jié)點編序如下圖所示v4v3v1v20100001010011100AG’=G’的鄰接矩陣變?yōu)椋?021/6/27鄰接矩陣對于僅僅結(jié)點編序不同的圖，是同構(gòu)的

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

G2

存在置換矩陣P，使得

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

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

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

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

aik

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

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

akjn

k=1n

k=1零圖連通的簡單完全圖對稱矩陣出度入度2021/6/27鄰接矩陣定理：設(shè)A為簡單圖G的鄰接矩陣，則An中的i行j列的元素

aijn等于G中聯(lián)結(jié)vi和vj的長度為n的鏈（路）的數(shù)目證明：1)當(dāng)n=1時，An=A1=A，定理成立2)設(shè)n=k時定理成立，即aijk為G中聯(lián)結(jié)vi和vj的長度為k的鏈的數(shù)目3)當(dāng)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ù)目2021/6/27鄰接矩陣?yán)?.3.3圖G=<V,E>如圖所示，求A,A2,A3,A40101001010010100A=v1v3v4v20110100102010010A2=1011020101201001A3=1202012020120201A4=2021/6/27鄰接矩陣由上面的定理可知：

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

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

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

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

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

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

Bn

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

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

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

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

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

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

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

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

可達(dá)vj

0, vi

不可達(dá)vj2021/6/27可達(dá)矩陣可達(dá)矩陣P=(pij)的計算之一：通過Bn

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

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

pij= 1, bij≠

0

0, bij＝

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

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

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

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