離散數(shù)學(xué) 課件 第7章 圖

第7章 圖第1節(jié) 圖的基本概念第2節(jié) 子圖與圖的運(yùn)算第3節(jié) 路徑、回路和連通性第4節(jié) 圖的矩陣表示第5節(jié) 歐拉圖和哈密頓圖第6節(jié) 平面圖與歐拉公式第7節(jié) 二部圖與匹配第8節(jié) 樹第9節(jié) 根樹及其應(yīng)用第1節(jié) 圖的基本概念1、圖的定義2、無向圖、有向圖、混合圖3、鄰接結(jié)點(diǎn)、鄰接邊4、自環(huán)、平行邊、簡單圖5、度（入度、出度）6、奇結(jié)點(diǎn)、偶結(jié)點(diǎn)7、孤立結(jié)點(diǎn)、端點(diǎn)（懸掛點(diǎn)）、懸掛邊8、零圖、平凡圖、d度正則圖、完全圖1、圖的定義圖G是一個(gè)三元組:<>ΨGV(G),E(G),非空結(jié)點(diǎn)集合邊的集合從E(G)到結(jié)點(diǎn)無序偶（有序偶）集合上的函數(shù)有向邊、無向邊邊的曲、直、長、短以及結(jié)點(diǎn)的位置是無關(guān)緊要的ΨG(ei)=(vi,vj)結(jié)點(diǎn)的無序偶無向邊用連接vi和vj的無向線段表示ΨG(ei)=<vi,vj>結(jié)點(diǎn)的有序偶有向邊用連接vi和vj的有向線段表示vi為邊ei的起點(diǎn)vj為邊ei的終點(diǎn)vivjvivjeiei圖的舉例G=<V(G),E(G),ΨG>V(G)={a,b,c,d}E(G)={e1,e2,

e3,

e4,

e5,

e6}ΨG(e1)=(a,b)，ΨG(e2)=(a,c)ΨG(e3)=(b,d)ΨG(e4)=(b,c)ΨG(e5)=(d,c)，ΨG(e6)=(a,d)請畫出對應(yīng)的無向圖。abdce1e2e3e4e5e6abdce1e2e3e4e5e62、無向圖、有向圖、混合圖（1）有向圖：若圖G中所有的邊都是有向邊。（2）無向圖：若圖G中所有的邊都是無向邊。（3）混合圖：若圖G中一些邊是有向邊，另一些邊是無向邊。只討論有向圖和無向圖3、鄰接結(jié)點(diǎn)、鄰接邊關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的兩條邊鄰接結(jié)點(diǎn):由一條邊相連接的兩個(gè)結(jié)點(diǎn)vivjeivi和vj鄰接鄰接邊:vivjeiei和ej鄰接vkej鄰接結(jié)點(diǎn)、鄰接邊舉例 a、b、c、d四個(gè)結(jié)點(diǎn)中的任意兩個(gè)結(jié)點(diǎn)都是鄰接結(jié)點(diǎn)；

e1和e5不鄰接；

e4和e6不鄰接；

e2和e3不鄰接。4、自環(huán)、平行邊、簡單圖圖G=<V(G),E(G),ΨG>（1）自環(huán):關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的邊（2）平行邊:關(guān)聯(lián)于同一對結(jié)點(diǎn)的兩條邊（3）簡單圖:無平行邊和自環(huán)的圖平行邊舉例

在有向圖中，如果邊e1和e2關(guān)聯(lián)于同一對結(jié)點(diǎn)，但方向相反，則它們不是平行邊。5、度（入度、出度）圖G=<V(G),E(G),ΨG>v∈V(G)與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù)（1）v的度:G是無向圖,deg(v)（2）v的出度:G是有向圖,以v為起點(diǎn)的邊的條數(shù)deg+(v)v的入度:以v為終點(diǎn)的邊的條數(shù)deg-(v)v的度:v的出度和入度之和deg(v)自環(huán)的度

對于無向圖中的一個(gè)自環(huán)，給該結(jié)點(diǎn)的度增加2； 對于有向圖中的自環(huán)，給該結(jié)點(diǎn)增加一個(gè)出度和一個(gè)入度，故該結(jié)點(diǎn)的度也增加2。結(jié)點(diǎn)度的舉例給出圖1各結(jié)點(diǎn)的度；給出圖2各結(jié)點(diǎn)的出度、入度、度。解答deg(v1)=deg(v4)=3deg(v2)=deg(v3)=2deg+(v1)=1,deg-(v1)=1,deg(v1)=2deg+(v2)=1,deg-(v2)=2,deg(v2)=3deg+(v3)=2,deg-(v3)=0,deg(v3)=2deg+(v4)=2,deg-(v4)=1,deg(v4)=3deg+(v5)=0,deg-(v5)=2,deg(v5)=2(n,m)圖圖n個(gè)結(jié)點(diǎn)m條邊(n,m)圖定理(n,m)圖所有結(jié)點(diǎn)的度之和等于邊數(shù)的兩倍證明因?yàn)椋好織l邊必關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)一條邊給它所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)的度各增加1為整個(gè)圖的度數(shù)增加2所以：結(jié)點(diǎn)的度數(shù)總和恰好為邊數(shù)的兩倍。定理驗(yàn)證m=5deg(v1)+deg(v2)+deg(v3)+deg(v4)=3+2+2+3=10=2m定理(n,m)有向圖所有結(jié)點(diǎn)的出度之和等于入度之和等于邊數(shù)定理驗(yàn)證m=6deg+(v1)+deg+(v2)+deg+(v3)+deg+(v4)+deg+(v5)=1+1+2+2+0=mdeg-(v1)+deg-(v2)+deg-(v3)+deg-(v4)+deg-(v5)=1+2+0+1+2=m6、奇結(jié)點(diǎn)、偶結(jié)點(diǎn)偶結(jié)點(diǎn)：奇結(jié)點(diǎn)：度數(shù)為奇數(shù)的結(jié)點(diǎn)度數(shù)為偶數(shù)的結(jié)點(diǎn)定理在任何圖中，必有偶數(shù)個(gè)奇結(jié)點(diǎn)。證明圖G=<V(G),E(G),ΨG>|E|=mV1:V2:V中奇結(jié)點(diǎn)集合V中偶結(jié)點(diǎn)集合偶結(jié)點(diǎn)的度數(shù)之和偶數(shù)偶數(shù)奇結(jié)點(diǎn)的度數(shù)之和偶數(shù)|V1|偶數(shù)偶數(shù)個(gè)奇結(jié)點(diǎn)7、孤立結(jié)點(diǎn)、端點(diǎn)（懸掛點(diǎn)）、懸掛邊圖G=<V(G),E(G),ΨG>v∈V(G)（1）孤立結(jié)點(diǎn):deg(v)=0（2）端點(diǎn):deg(v)=1懸掛點(diǎn)（3）懸掛邊:與懸掛點(diǎn)關(guān)聯(lián)的邊孤立結(jié)點(diǎn)、懸掛點(diǎn)、懸掛邊舉例V5是懸掛點(diǎn)；(v4,v5)是懸掛邊;V6是孤立結(jié)點(diǎn)8、零圖、平凡圖、d度正則圖、完全圖G=<V(G),E(G),ΨG>:簡單無向圖（1）零圖:E=Φ(n,0)圖（2）平凡圖:|V|=1E=Φ(1,0)圖（3）d度正則圖:每個(gè)結(jié)點(diǎn)的度均為d（4）完全圖：任意兩點(diǎn)間恰有一條邊連接Kn舉例第2節(jié) 子圖與圖的運(yùn)算一、子圖二、圖的運(yùn)算一、子圖1、子圖2、真子圖3、生成子圖4、結(jié)點(diǎn)導(dǎo)出子圖5、邊導(dǎo)出子圖1、子圖兩個(gè)圖G=<V,E,

>G′=<V′,E′,

′>V′VE′

EG′是G的子圖2、真子圖兩個(gè)圖G=<V,E,

>G′=<V′,E′,

′>V′VE′EG′是G的真子圖3、生成子圖兩個(gè)圖G=<V,E,

>G′=<V′,E′,

′>V′=VE′

EG′是G的生成子圖子圖的舉例4、結(jié)點(diǎn)導(dǎo)出子圖G=<V,E,

>V′VV′≠φV′為結(jié)點(diǎn)集合起點(diǎn)和終點(diǎn)均在V′中的邊的全體為邊集合由V′導(dǎo)出的G的子圖G[V′]V′V導(dǎo)出子圖G[V-V′]G-V′結(jié)點(diǎn)導(dǎo)出子圖舉例求:(1)由結(jié)點(diǎn)集合V′={a,b,d,e}導(dǎo)出的G的子圖G[{a,b,d,e}](2)G-{a,d}解答5、邊導(dǎo)出子圖G=<V,E,

>E′EE′≠φV′={v|v

V∧(

e)(eE′∧v與e關(guān)聯(lián))}以V′為結(jié)點(diǎn)集合以E′為邊集由E′導(dǎo)出的子圖邊導(dǎo)出子圖舉例求:由邊集合E′={e1,e2,e5,e7}導(dǎo)出的G的子圖G[{e1,e2,e5,e7}]解答二、圖的運(yùn)算1、可運(yùn)算的2、邊不相交的3、點(diǎn)不相交的4、圖的交5、圖的并6、圖的差7、圖的環(huán)和8、相對于圖G的補(bǔ)圖9、相對于完全圖的補(bǔ)圖1、可運(yùn)算的G1=<V1,E1,

1>G2=<V2,E2,

2>同為無向圖或同為有向圖對任意的e

E1∩E2

1(e)=2(e)G1與G2是可運(yùn)算的可運(yùn)算的舉例問：G1和G2是否是可運(yùn)算的？解答E1∩E2={e1,e2,e5}

1(e1)=(a,b)

2(e1)=(a,b)

1(e2)=(a,d)

2(e2)=(a,d)

1(e5)=(b,d)

2(e5)=(b,d)G1和G2是可運(yùn)算的2、邊不相交的G1=<V1,E1,

1>G2=<V2,E2,

2>同為無向圖或同為有向圖G1與G2是不相交的E1∩E2=φV1∩V2=φG1與G2是邊不相交E1∩E2=φ3、點(diǎn)不相交的G1與G2是點(diǎn)不相交的G1=<V1,E1,

1>G2=<V2,E2,

2>同為無向圖或同為有向圖V1∩V2=φ4、圖的交G1=<V1,E1,

1>G2=<V2,E2,

2>是可運(yùn)算的V1∩V2為結(jié)點(diǎn)集E1∩E2為邊集合G1和G2的交G1∩G25、圖的并G1=<V1,E1,

1>G2=<V2,E2,

2>是可運(yùn)算的V1∪

V2為結(jié)點(diǎn)集E1∪

E2為邊集合G1和G2的并G1∪

G26、圖的差G1=<V1,E1,

1>G2=<V2,E2,

2>是可運(yùn)算的G1與G2的差:在G1中去掉G2的邊所得到的圖G1-

G27、圖的環(huán)和G1=<V1,E1,

1>G2=<V2,E2,

2>是可運(yùn)算的V1∪

V2為結(jié)點(diǎn)集E1⊕

E2為邊集合G1和G2的環(huán)和G1⊕

G2圖運(yùn)算的舉例與如下圖所示，求：G1∩G2

G1∪G2G1-G2G2-G1，G1⊕G2

。G1∩G2V1∩V2E1∩E2={a,b,d}={e1,e2,e5}G1∪G2V1∪V2{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}={a,b,c,d,e}E1∪E2=G1-G2G2

–G1G1⊕G2E1⊕

E2=V1∪V2={a,b,c,d,e}{e3,e4,e6,e7,e8,e9,e10}8、相對于圖G的補(bǔ)圖G=<V,E>的子圖:G′=<V′,E′>:給定另一個(gè)圖G"=<V",E">（1）E"＝E-E′（2）V"是E"中的邊所關(guān)聯(lián)的結(jié)點(diǎn)集合G"是子圖G′的相對于圖G的補(bǔ)圖解釋(1)E′∩E"＝φ(2)E′∪E"＝E(3)V"僅是E"中的邊所關(guān)聯(lián)的結(jié)點(diǎn)集合，不包含別的結(jié)點(diǎn):G′∪G"＝G(4)G′與G"的關(guān)系不是互逆的。相對補(bǔ)圖的舉例圖G和圖G′如下圖所示:求圖G′相對于圖G的補(bǔ)圖。解答E"＝E-E′={(a,e),(c,e),(d,e)}V"＝{a,c,d,e}圖G′相對于圖G的補(bǔ)圖為G"G"相對于圖G的補(bǔ)圖為G"′不是G′沒有結(jié)點(diǎn)e9、相對于完全圖的補(bǔ)圖補(bǔ)圖是互逆的給定一個(gè)圖GG中所有結(jié)點(diǎn)能使G成為完全圖所添加的邊圖G相對于完全圖的補(bǔ)圖G的補(bǔ)圖補(bǔ)圖舉例求G1和G2的補(bǔ)圖。解答解答第3節(jié) 路徑、回路和連通性一、路徑二、連通性一、路徑1、路徑2、可達(dá)的、不可達(dá)的1、路徑(1)路徑(2)回路(3)簡單路徑、基本路徑(1)路徑路徑是結(jié)點(diǎn)和邊的交替序列圖G=<V,E>v0,v1…vnVe1,e2…enEei:關(guān)聯(lián)vi-1和vi序列v0e1v1e2…envn:從v0到vn的路路徑路徑的起點(diǎn)路徑的終點(diǎn)路徑的長度:路徑中邊的數(shù)目(2)回路起點(diǎn)和終點(diǎn)為同一個(gè)結(jié)點(diǎn)的路徑(3)簡單路徑、基本路徑簡單路徑:簡單回路:基本路徑:基本回路:邊不重復(fù)的路徑邊不重復(fù)的回路點(diǎn)不重復(fù)的路徑點(diǎn)不重復(fù)的回路路徑舉例(1)AaAcBgChF:(2)AbDdEeBfChF:(3)AbDdEeBcA:從A到F的路徑長度為4簡單路徑不是基本路徑從A到F的路徑長度為5簡單路徑基本路徑從A到A的回路長度為4簡單回路基本回路路徑舉例v1e2v2e3v3e4v4v4e1v1e2v2e3v3e4v4e1v1簡單路徑基本路徑不是基本路徑不是簡單路徑定理尋找基本路徑的方法：v和v’是圖G中的結(jié)點(diǎn)存在從v到v’的路徑存在從v到v’的基本路徑從路徑中去掉所有的回路證明從v到v′存在路徑Pvv′:

v0e1v1e2…elvlvv′若Pvv′不是基本路徑結(jié)點(diǎn)vi在該路徑中不止一次出現(xiàn)v0e1v1e2…eivi

ei+1

…

ejvjej+1…elvlvi=vj在該路徑中去掉從vi到vj的邊v0e1v1e2…eiviej+1…elvl從v0到vl的路徑如此反復(fù)去掉所有的回路從v0到vl的基本路徑定理應(yīng)用舉例(1)ae2be10de9ae2be4c:(2)ae1ae2be4c:求從a到c的基本路徑是從a到c的一條路徑,是從a到c的一條路徑,求從a到c的基本路徑解答(1)ae2be10de9ae2be4c:不是基本路徑去掉回路ae2be10de9aae2be4c基本路徑(2)ae1ae2be4c:不是基本路徑去掉回路ae1aae2be4c基本路徑定理n階圖中的基本路徑的長度小于n。證明基本路徑:點(diǎn)不重復(fù)的路徑在一個(gè)基本路徑中有l(wèi)個(gè)不同的結(jié)點(diǎn)v0,v1,…,vl-1有l(wèi)-1條邊:e1,e2,…,el-1v0e1v1e2…el-1vl-1基本路徑n階圖:有n個(gè)不同的結(jié)點(diǎn)最多有n-1條邊出現(xiàn)在基本路徑上n階圖中的基本路徑的長度小于n2、可達(dá)的、不可達(dá)的v1,v2:圖G中的結(jié)點(diǎn)存在從v1到v2的路徑從v1到v2

是可達(dá)的否則:從v1到v2不可達(dá)v1可達(dá)v2

在無向圖中:在有向圖中:v2可達(dá)v1

V2不一定可達(dá)v1

二、連通性1、連通圖2、基礎(chǔ)圖3、強(qiáng)連通、單向連通、弱連通4、極大子圖5、分支1、連通圖G:無向圖任意兩個(gè)結(jié)點(diǎn)都相互可達(dá)連通圖否則:G是非連通圖2、基礎(chǔ)圖把每條有向邊改為無向邊而得到的無向圖有向圖的基礎(chǔ)圖3、強(qiáng)連通、單向連通、弱連通G:有向圖(1)強(qiáng)連通圖:任意兩結(jié)點(diǎn)均互相可達(dá)(2)單向（側(cè)）連通圖:任意兩結(jié)點(diǎn)必有一結(jié)點(diǎn)可達(dá)另一個(gè)結(jié)點(diǎn)(3)弱連通圖:G的基礎(chǔ)圖是連通的連通性舉例

判斷圖G1,G2,G3是強(qiáng)連通圖、單向連通圖還是弱連通圖？解答v2不可達(dá)v3v3也不可達(dá)v2G1不是單向連通圖G1的基礎(chǔ)圖是連通圖G1是弱連通圖解答v1可達(dá)v3v3不可達(dá)v1G2不是強(qiáng)連通圖v2可達(dá)v3v2可達(dá)v1G2是單向連通圖解答v1可達(dá)v2v2可達(dá)v1v1可達(dá)v3v3可達(dá)v1v2可達(dá)v3v3可達(dá)v2G3是強(qiáng)連通圖4、極大子圖G’:G的子圖G’具有連通性對于G的任意的具有連通性的子圖G’’G’

G’’G’=G’’G’是G的極大連通子圖強(qiáng)連通性強(qiáng)連通性強(qiáng)連通單向連通性單向連通性單向連通弱連通性弱連通性弱連通5、分支無向圖G的極大連通子圖

G的分支（分圖）:G的強(qiáng)分支（強(qiáng)分圖）:有向圖G的極大強(qiáng)連通子圖G的單向分支（單向分圖）:有向圖G的極大單向連通子圖G的弱分支（弱分圖）:有向圖G的極大弱連通子圖定理連通無向圖恰有一個(gè)分支非連通無向圖有一個(gè)以上的分支舉例圖G是一個(gè)連通無向圖其只有一個(gè)極大連通子圖，就是其本身G。舉例圖G是一個(gè)非連通無向圖其有兩個(gè)極大連通子圖G1和G2。定理強(qiáng)連通有向圖恰有一個(gè)強(qiáng)分支非強(qiáng)連通有向圖有一個(gè)以上的強(qiáng)分支單向連通單向分支單向連通單向分支弱連通弱連通弱分支弱分支定理G=<V,E>:簡單有向圖每一個(gè)結(jié)點(diǎn)都恰處于一個(gè)強(qiáng)分支中分支舉例求G1、G2的強(qiáng)分支、單向分支、弱分支。解答解答定理無向圖G（連通或不連通）恰有兩個(gè)奇結(jié)點(diǎn)必有連接此兩結(jié)點(diǎn)的路徑證明設(shè)G中的兩個(gè)奇結(jié)點(diǎn)是v1和v2(1)若G是連通圖，則v1和v2之間必有路徑；(2)若G是非連通圖，則G至少有兩個(gè)以上的分支因?yàn)?，在任何一個(gè)圖中必有偶數(shù)個(gè)奇結(jié)點(diǎn)所以：v1和v2必處于同一個(gè)分支中，即：V1和v2之間必有路徑。第4節(jié) 圖的矩陣表示一、鄰接矩陣二、可達(dá)性矩陣三、完全關(guān)聯(lián)矩陣一、鄰接矩陣1、簡單無向圖的鄰接矩陣2、簡單有向圖的鄰接矩陣3、矩陣AAT4、矩陣ATA5、矩陣Am1、簡單無向圖的鄰接矩陣G:簡單無向圖n階方陣A=(aij)n×nV={v1,v2,…,vn}鄰接矩陣:aij=(vi,vj)

E10否則鄰接矩陣舉例寫出簡單無向圖G對應(yīng)的鄰接矩陣A。A=abcdeabcde1111111111111100000000000簡單無向圖鄰接矩陣的特點(diǎn)(1)主對角線均為0的對稱陣；(2)每一行（列）中“1”的個(gè)數(shù)是該行所對應(yīng)的結(jié)點(diǎn)的度；(3)所有元素均為“0”的鄰接矩陣對應(yīng)的是零圖;(4)除主對角線外所有元素均為“1”的鄰接矩陣對應(yīng)的是完全圖。2、簡單有向圖的鄰接矩陣G:簡單有向圖n階方陣A=(aij)n×nV={v1,v2,…,vn}鄰接矩陣:aij=<vi,vj>

E10否則鄰接矩陣舉例寫出簡單有向圖G對應(yīng)的鄰接矩陣A。A=v1v2v3v4v1v2v3v40101111010100000簡單有向圖鄰接矩陣的特點(diǎn)(1)不一定是對稱陣；(2)每一行中“1”的個(gè)數(shù)是該行所對應(yīng)的結(jié)點(diǎn)的出度；(3)每一列中“1”的個(gè)數(shù)是該列所對應(yīng)的結(jié)點(diǎn)的入度；(4)第i行中“1”的個(gè)數(shù)與第i列中“1”的個(gè)數(shù)之和，恰為記點(diǎn)vi的度。二、可達(dá)性矩陣1、可達(dá)性矩陣P2、求可達(dá)性矩陣P的方法1、可達(dá)性矩陣PG:簡單有向圖V={v1,v2,…,vn}n階方陣P=(pij)n×nG的可達(dá)性矩陣pij=10從vi到vj至少存在一條路徑否則2、求可達(dá)性矩陣P的方法(1)回憶兩個(gè)定理(2)求可達(dá)性矩陣P的方法(1)回憶兩個(gè)定理若存在從vi到vj的路徑，則存在從vi到vj的基本路徑；n階圖的基本路徑長度小于n;(2)求可達(dá)性矩陣P的方法A：aij表示從vi到vj長度為1的路徑的數(shù)目；A2:aij(2)表示從vi到vj長度為2的路徑的數(shù)目；……An:aij(n)表示從vi到vj長度為n的路徑的數(shù)目；令：Bn=A+A2+…+An

其中：

Bn中第i行第j列的記入值bij表明：從vi到vj長度小于或等于n的路徑的數(shù)目若bij≠0，則表明從vi到vj可達(dá)。求可達(dá)性矩陣P的方法（續(xù)）A:簡單有向圖G的鄰接矩陣（1）A2=A∧AA3=A2∧A,…,An=An-1∧A（2）P=A∨A2∨…∨An三、完全關(guān)聯(lián)矩陣：1、無向圖的完全關(guān)聯(lián)矩陣2、有向圖的完全關(guān)聯(lián)矩陣1、無向圖的完全關(guān)聯(lián)矩陣G:無向圖V={v1,v2,…,vn}E={e1,e2,…,em}Ae=(aij)n×m圖G的完全關(guān)聯(lián)矩陣aij=10vi關(guān)聯(lián)ej否則無向圖的完全關(guān)聯(lián)矩陣舉例求無向圖G的完全關(guān)聯(lián)矩陣AeAe=v1v2v3v41110111000001100e1e2e3e4e51001無向圖的完全關(guān)聯(lián)矩陣的特點(diǎn)（1）每一列中只有兩個(gè)“1”；（2）每一行中“1”的個(gè)數(shù)是該結(jié)點(diǎn)的度數(shù)；（3）若某行中的元素均為“0”，則該行所對應(yīng)的結(jié)點(diǎn)是孤立結(jié)點(diǎn)；（4）平行邊所對應(yīng)的兩列相同；2、有向圖的完全關(guān)聯(lián)矩陣G:有向圖V={v1,v2,…,vn}E={e1,e2,…,em}Ae=(aij)n×m圖G的完全關(guān)聯(lián)矩陣aij=10vi是ej的起點(diǎn)-1vi是ej的終點(diǎn)Vi與ej不關(guān)聯(lián)有向圖的完全關(guān)聯(lián)矩陣舉例求有向圖G的完全關(guān)聯(lián)矩陣AeAe=v1v2v3v4-1-10-111000001100-1e1e2e3e4e501-10v5e61-100000000有向圖的完全關(guān)聯(lián)矩陣的特點(diǎn)（1）每列元素之和為“0”；（2）每一行中“1”的個(gè)數(shù)是該行所對應(yīng)結(jié)點(diǎn)的出度；（3）每一行中“-1”的個(gè)數(shù)是該行所對應(yīng)結(jié)點(diǎn)的入度；（4）全為“0”的行所對應(yīng)的結(jié)點(diǎn)為孤立結(jié)點(diǎn)。第5節(jié) 歐拉圖和哈密頓圖一、歐拉圖二、哈密頓圖一、歐拉圖1、歐拉路徑2、歐拉回路3、歐拉圖4、有向歐拉圖歐拉圖的起源1、歐拉路徑G:無孤立結(jié)點(diǎn)的無向圖經(jīng)過圖中每條邊一次且僅一次路徑歐拉路徑:2、歐拉回路G:無孤立結(jié)點(diǎn)的無向圖歐拉回路:經(jīng)過圖中每條邊一次且僅一次回路3、歐拉圖具有歐拉回路的圖叫歐拉圖。歐拉圖舉例判斷圖G1和G2是否是歐拉圖？解答G1：歐拉回路1234563726781歐拉圖G2：125462341歐拉回路歐拉圖定理無向連通圖G是歐拉圖G的每個(gè)結(jié)點(diǎn)均為偶結(jié)點(diǎn)哥尼斯堡七橋問題deg(A)=deg(B)=deg(D)=3，deg(C)=5哥尼斯堡七橋問題無解。歐拉圖應(yīng)用舉例

環(huán)衛(wèi)工人清掃街道，清掃路線如圖所示，試問是否存在清掃路線使環(huán)衛(wèi)工人從V1出發(fā)通過所有路線而不重復(fù)且最后回到V1。

解答

由于圖中每個(gè)結(jié)點(diǎn)均為偶次數(shù)，故由定理可知這樣的一條清掃路線是存在的。

(v1,v5,v11,v7,v12,v8,v10,v6,v9,v11,v12,v10,v9,v5,v2,v6,v4,v8,v3,v7,v1)deg(v1)=deg(v2)=deg(v3)=deg(v4)=2，deg(v5)=deg(v6)=deg(v7)=deg(v8)=deg(v9)=deg(v10)=deg(v11)=deg(v12)=4定理無向連通圖G中結(jié)點(diǎn)vi與vj間存在歐拉路徑vi與vj的度數(shù)均為奇數(shù)其它結(jié)點(diǎn)的度數(shù)均為偶數(shù)定理應(yīng)用舉例一筆畫問題：判別圖(1)、(2)是否可以一筆畫。解答圖(1)A、B為奇結(jié)點(diǎn)C,D,E為偶結(jié)點(diǎn)歐拉路徑:AEDCBECAB解答圖(2)A、B為奇結(jié)點(diǎn)其余各點(diǎn)為偶結(jié)點(diǎn)A與B兩點(diǎn)間存在歐拉路徑，即從A到B可以一筆畫。定理應(yīng)用舉例判斷圖（3）是否可以一筆畫。A,B,C,D均為奇結(jié)點(diǎn)圖(3)中無歐拉路徑，因此不可以一筆畫。4、有向歐拉圖G:有向圖經(jīng)過圖中每條邊一次且僅一次的有向路徑有向歐拉路徑:有向歐拉回路:經(jīng)過圖中每條邊一次且僅一次的有向回路有向歐拉圖:有有向歐拉回路的有向圖定理

一個(gè)連通有向圖G是有向歐拉圖對G中的所有結(jié)點(diǎn)v,有：d+(v)=d-(v)有向歐拉圖舉例

判斷圖G1和G2是否為有向歐拉圖，如果是，請給出有向歐拉回路。圖G1圖G2解答d+(v1)=d-(v1)=1d+(v2)=d-(v2)=2d+(v3)=d-(v3)=1d+(v4)=d-(v4)=2d+(v5)=d-(v5)=2是有向歐拉圖有向歐拉回路:v1e1v2e3v4e7v5e5v1e6v4e8v5e4v3e2v1解答d+(v4)=1≠d-(v4)=3d+(v5)=3≠d-(v5)=1不是有向歐拉圖二、哈密頓圖1、哈密頓圖的起源2、哈密頓圖1、哈密頓圖的起源周游世界游戲： 從某個(gè)城市出發(fā)，經(jīng)過每個(gè)城市一次且僅一次，最后回到出發(fā)點(diǎn)。2、哈密頓圖G:無向圖經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的路徑哈密頓路徑:哈密頓回路:經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的回路哈密頓圖:有哈密頓回路的圖哈密頓圖舉例

判斷圖G1和G2是否為哈密頓圖，如果是，請給出哈密頓回路。解答G1：1a2b3c4d5e1哈密頓回路G2：是哈密頓圖不是哈密頓圖無哈密頓回路第6節(jié) 平面圖與歐拉公式1、平面圖2、平面圖的區(qū)（面）3、相鄰區(qū)1、平面圖G=<V,E>:無向圖G的所有結(jié)點(diǎn)和邊均能畫在一個(gè)平面上任意兩條邊除了端點(diǎn)外沒有任何交叉平面圖否則:G為非平面圖平面圖舉例說明G1是平面圖G2是非平面圖。解答2、平面圖的區(qū)（面）G:連通的平面圖由圖中的邊所包圍的區(qū)域，在區(qū)域內(nèi)既不包含結(jié)點(diǎn)也不包含圖的邊面:內(nèi)區(qū)無限面:一個(gè)平面圖外部區(qū)域外區(qū)面的邊界:包圍該面的諸邊所構(gòu)成的回路面的周界長度:圍成一個(gè)面所含邊的數(shù)目平面圖的面舉例平面圖G1有4個(gè)區(qū)：R0,R1,R2,R3R0是無限面；

平面圖G1有5個(gè)區(qū)：R0,R1,R2,R3,R4，R0是無限面；平面圖的面舉例

同一圖的不同畫法，它的區(qū)也不同，但它們所含區(qū)的個(gè)數(shù)是相同的。G1:R0是無限面R1,R2,R3是內(nèi)區(qū)G1′:R3是無限面R1,R2,R0是內(nèi)區(qū)3、相鄰區(qū)兩個(gè)區(qū)的邊界至少有一條公共邊兩個(gè)區(qū)是相鄰的否則:兩個(gè)區(qū)是不相鄰的相鄰區(qū)舉例R0和R1、R2、R3

、R4相鄰R1和R0、R3相鄰R2和R0、R3相鄰R3和R0、R1、R2

相鄰R4和R0

相鄰定理（歐拉公式）n-m+r=2G:連通的平面圖n:結(jié)點(diǎn)數(shù)m:邊數(shù)r:面數(shù)歐拉公式解釋

歐拉公式只適用于連通平面圖，是必要條件，即：(1)任何一個(gè)連通平面圖都滿足歐拉公式；(2)不滿足歐拉公式的圖一定不是平面圖；(3)滿足歐拉公式的圖不一定是平面圖。第7節(jié) 二部圖與匹配一、二部圖二、匹配一、二部圖1、二部圖的定義2、完全二部圖1、二部圖的定義G=<V,E>:無向圖{V1,V2}:V的劃分使得Vi(i=1,2)中任何兩個(gè)結(jié)點(diǎn)都不鄰接二部圖V1,V2:互補(bǔ)結(jié)點(diǎn)子集。二部圖舉例工作分配問題：4個(gè)待業(yè)人員a1,a2,a3,a4，a1a2a3a46項(xiàng)工作任務(wù)p1,p2,p3,p4,p5,p6p2p3p4p5p1p6a1,a2,a4能勝任p2,p5a3能勝任p1,p2,p3,p4,p62、完全二部圖V1,V2:簡單二部圖的互補(bǔ)結(jié)點(diǎn)子集V1中的每個(gè)結(jié)點(diǎn)與V2中的每個(gè)結(jié)點(diǎn)鄰接G為完全二部圖|V1|=m|V2|=nKm,n完全二部圖舉例第8節(jié) 樹1、樹、樹葉、分枝結(jié)點(diǎn)、樹枝2、最小連通圖3、森林4、生成樹、樹枝5、求一個(gè)連通圖G的生成樹的方法6、最小生成樹7、求最小生成樹的算法1、樹、樹葉、分枝結(jié)點(diǎn)、樹枝（1）樹:連通的且無回路的無向圖T（2）樹葉:樹中度數(shù)為1的結(jié)點(diǎn)（3）分枝結(jié)點(diǎn):樹中度數(shù)大于1的結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)（4）樹枝:樹中的邊樹的舉例判斷圖G1、G2、G3是否為樹？是不是有回路不是不連通2、最小連通圖G:連通圖G中去掉任何一條邊G變?yōu)椴贿B通的圖最小連通圖定理G=(n,m):無向圖以下關(guān)于樹的定義是等價(jià)的：（1）G無回路且連通（2）G無回路且m=n-1（3）G連通且m=n-1；（4）G無回路但增加一條邊，得到且僅得到一條回路；（5）G是最小連通圖;（6）G中每一對結(jié)點(diǎn)之間有且僅有一條路。證明:(2)

(3)G無回路且m=n-1

G連通且m=n-1假設(shè)G不連通:設(shè)G有k個(gè)分支G1=(n1,m1),G2=(n2,m2),…,Gk=(nk,mk)n1+n2+…+nk=nm1+m2+…+mk=mG無回路每個(gè)分支連通且無回路m1=n1-1,m2=n2-1,…,mk=nk-1m=(n1-1)+(n2-1)+…+(nk-1)=n1+n2+…+nk

–k=n-kk=1G是連通的定理任意一棵樹至少有兩個(gè)樹葉。證明樹T=(n,m)，則m=n-1d(v1)+d(v2)+…+d(vn)=2m=2(n-1)=2n-2(1)假設(shè)T中各結(jié)點(diǎn)的度均大于或等于2，則：d(v1)+d(v2)+…+d(vn)≥2n＞2n-2，這與上式矛盾(2)假設(shè)T中只有1個(gè)結(jié)點(diǎn)的度為1，其余結(jié)點(diǎn)的度均大于1，則：d(v1)+d(v2)+…+d(vn)≥1+(n-1)×2=2n-2+1=2n-1＞2n-2，這與上式也矛盾所以：一棵樹中至少有兩個(gè)度為1的結(jié)點(diǎn)，即至少有兩片樹葉。3、森林

如果非連通無向圖G的每個(gè)分支都是樹，則稱G為森林。若森林的分支數(shù)為k,則：m=n-k4、生成樹、樹枝、連枝生成樹不唯一(1)生成樹:無向圖G的生成子圖T是一棵樹G的生成樹（2）樹枝：G的生成樹T中的邊（3）連枝：屬于G但不屬于T的邊生成樹舉例求圖G的生成樹圖T1和T2均為G的生成樹。定理圖G有生成樹G連通5、求連通圖G的生成樹的方法（1）避回路法（2）破回路法（1）避回路法①任意取圖G中的一條邊e1，再取一條邊e2，使得e1和e2不構(gòu)成回路；②再取一條邊e3，使得e3和e1、e2不構(gòu)成回路；③如此下去，最后得到的不含回路的連通生成子圖即是G的一棵生成樹。避回路法從G中取n-1條邊避回路法舉例用避回路法求圖G的生成樹。a(1)取邊a;(2)取邊b,且邊b與邊a不形成回路；b(3)邊c與邊b、邊a形成回路，避開；(4)取邊e,且邊e與邊a、b不形成回路；e(5)取邊d,且邊d與邊a、b、e不形成回路；dn=5,共取n-1=5-1=4條邊，結(jié)束。生成樹不唯一（2）破回路法（1）在G中任取一個(gè)回路，去掉該回路中的一條邊；（2）再取一回路，再去掉該回路中的一條邊；（3）如此繼續(xù)下去，最后得到的不含回路的連通生成子圖即是G的一棵生成樹。破回路法從G中刪掉m-(n-1)條邊破回路法舉例用破回路法求圖G的生成樹。(1)取回路(a,b,c)去掉c邊(2)取回路(a,b,g,e)去掉g邊(3)取回路(a,b,d,f,e)去掉f邊n=5,m=7,共去掉m-(n-1)=7-(5-1)=3條邊6、最小生成樹<G,W>:加權(quán)圖加權(quán)長度:所有邊的加權(quán)長度之和最小生成樹:G的所有生成樹中加權(quán)長度最小的生成樹7、求最小生成樹的算法（1）避回路法（2）破回路法（1）避回路法①選取權(quán)值最小的邊；②若m=n-1，則停止；否則③；③已選擇的邊為e1,e2,…,ei{e1,e2,…,ei,ei+1}中無回路ei+1:不同于e1,e2,…,ei的邊權(quán)值最小避回路法求最小生成樹舉例用避回路法求圖G的最小生成樹解答abcdef(1)選擇權(quán)值為1的邊(c,d);1(2)選擇權(quán)值為2的邊(b,f);2(3)選擇權(quán)值為3的邊(b,c);3(4)選擇權(quán)值為4的邊(a,b);4(5)權(quán)值為5的邊(a,f),形成回路,避開權(quán)值為6的邊(a,c),形成回路,避開;權(quán)值為7的邊(d,f),形成回路,避開;(6)選擇權(quán)值為8的邊(f,e);8加權(quán)長度＝1＋2＋3＋4＋8＝18最小生成樹（2）破回路法（1）在G中任取一個(gè)回路，去掉該回路中權(quán)值最大的一條邊，得到一個(gè)子圖G1；（2）在G1中再取一回路，再去掉該回路中權(quán)值最大的一條邊，得到一個(gè)子圖G2

；（3）如此繼續(xù)下去，最后得到的不含回路的連通生成子圖即是G的一棵最小生成。破回路法求最小生成樹舉例用破回路法求圖G的最小生成樹解答(1)取回路(a,b,c,a)去掉權(quán)值最大的邊(a,c)(2)取回路(a,b,f,a)去掉權(quán)值最大的邊(a,f)解答（續(xù)）(3)取回路(b,c,e,f,b)去掉權(quán)值最大的邊(c,e)(4)取回路(d,e,f,d)去掉權(quán)值最大的邊(d,e)解答（續(xù)）(5)取回路(a,b,e,d,a)去掉權(quán)值最大的邊(a,d)(6)取回路(b,c,d,f,b)去掉權(quán)值最大的邊(d,f)求最小生成樹舉例求圖G的最小生成樹v5v4v3v2v1(1)選擇權(quán)值為3的邊(v1,v5);3(2)選擇權(quán)值為4的邊(v1,v4);4(3)選擇權(quán)值為4的邊(v4,v5);形成回路,避開(4)選擇權(quán)值為5的邊(v2,v5);5(5)選擇權(quán)值為6的邊(v3,v5);6加權(quán)長度為3+4+5+6＝18最小生成樹解答(2)v5v4v3v2v1(1)選擇權(quán)值為3的邊(v1,v5);3(2)選擇權(quán)值為4的邊(v4,v5);4(3)選擇權(quán)值為4的邊(v1,v4);形成回路,避開(4)選擇權(quán)值為5的邊(v2,v5);5(5)選擇權(quán)值為6的邊(v3,v5);6加權(quán)長度為3+4+5+6＝18最小生成樹不唯一，最小生成樹的加權(quán)長度相同第9節(jié) 根樹及其應(yīng)用1、有向樹2、根樹3、有序樹4、子樹5、m叉樹、完全m叉樹6、帶權(quán)二叉樹7、最優(yōu)二叉樹8、構(gòu)造具有t片樹葉的最優(yōu)二叉樹的方法1、有向樹

若一個(gè)有向圖在不考慮邊的方向時(shí)是一棵樹，則該有向圖稱為有向樹。2、根樹根樹:有向樹恰好有一個(gè)結(jié)點(diǎn)的入度為0其余所有結(jié)點(diǎn)的入度為1根葉：出度為0的結(jié)點(diǎn)分枝結(jié)點(diǎn):出度不為0的結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)結(jié)點(diǎn)的層次、樹的高度從根到葉結(jié)點(diǎn)的最大距離結(jié)點(diǎn)v的層次：從根到結(jié)點(diǎn)v的距離樹的高度：根樹舉例樹葉:樹根樹的高度：3v4,v5,v6,v7,v8,v10,v11,v12分枝結(jié)點(diǎn)：v0,v1,v2,v3,v9根結(jié)點(diǎn)是分枝結(jié)點(diǎn)3、有序樹同一層的結(jié)點(diǎn)次序從左到右，左為大根樹規(guī)定了每一層上的結(jié)點(diǎn)的次序子孫、兒子、兄弟子孫（后代）：由結(jié)點(diǎn)v可達(dá)的每個(gè)結(jié)點(diǎn)兒子：僅由一條邊可達(dá)的結(jié)點(diǎn)兄弟關(guān)系：所有由v經(jīng)一條邊就可達(dá)的結(jié)點(diǎn)間的關(guān)系有序樹舉例不考慮同一層上結(jié)點(diǎn)的次序，是同一棵樹兩棵不同的有序樹。大小4、子樹以v為根的子樹:任一結(jié)點(diǎn)v及其v的所有子孫從v出發(fā)的所有有向路徑中的邊子圖結(jié)點(diǎn)集邊集子樹舉例T1，T2，T3，T4均為T的子樹。5、m叉樹、完全m叉樹m叉樹