離散數學 課件 第7章 圖

第7章 圖第1節(jié) 圖的基本概念第2節(jié) 子圖與圖的運算第3節(jié) 路徑、回路和連通性第4節(jié) 圖的矩陣表示第5節(jié) 歐拉圖和哈密頓圖第6節(jié) 平面圖與歐拉公式第7節(jié) 二部圖與匹配第8節(jié) 樹第9節(jié) 根樹及其應用第1節(jié) 圖的基本概念1、圖的定義2、無向圖、有向圖、混合圖3、鄰接結點、鄰接邊4、自環(huán)、平行邊、簡單圖5、度（入度、出度）6、奇結點、偶結點7、孤立結點、端點（懸掛點）、懸掛邊8、零圖、平凡圖、d度正則圖、完全圖1、圖的定義圖G是一個三元組:<>ΨGV(G),E(G),非空結點集合邊的集合從E(G)到結點無序偶（有序偶）集合上的函數有向邊、無向邊邊的曲、直、長、短以及結點的位置是無關緊要的ΨG(ei)=(vi,vj)結點的無序偶無向邊用連接vi和vj的無向線段表示ΨG(ei)=<vi,vj>結點的有序偶有向邊用連接vi和vj的有向線段表示vi為邊ei的起點vj為邊ei的終點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)請畫出對應的無向圖。abdce1e2e3e4e5e6abdce1e2e3e4e5e62、無向圖、有向圖、混合圖（1）有向圖：若圖G中所有的邊都是有向邊。（2）無向圖：若圖G中所有的邊都是無向邊。（3）混合圖：若圖G中一些邊是有向邊，另一些邊是無向邊。只討論有向圖和無向圖3、鄰接結點、鄰接邊關聯(lián)同一個結點的兩條邊鄰接結點:由一條邊相連接的兩個結點vivjeivi和vj鄰接鄰接邊:vivjeiei和ej鄰接vkej鄰接結點、鄰接邊舉例 a、b、c、d四個結點中的任意兩個結點都是鄰接結點；

e1和e5不鄰接；

e4和e6不鄰接；

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

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

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

>G′=<V′,E′,

′>V′VE′

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

>G′=<V′,E′,

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

>G′=<V′,E′,

′>V′=VE′

EG′是G的生成子圖子圖的舉例4、結點導出子圖G=<V,E,

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

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

V∧(

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

1>G2=<V2,E2,

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

E1∩E2

1(e)=2(e)G1與G2是可運算的可運算的舉例問：G1和G2是否是可運算的？解答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是可運算的2、邊不相交的G1=<V1,E1,

1>G2=<V2,E2,

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

1>G2=<V2,E2,

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

1>G2=<V2,E2,

2>是可運算的V1∩V2為結點集E1∩E2為邊集合G1和G2的交G1∩G25、圖的并G1=<V1,E1,

1>G2=<V2,E2,

2>是可運算的V1∪

V2為結點集E1∪

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

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

1>G2=<V2,E2,

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

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

1>G2=<V2,E2,

2>是可運算的V1∪

V2為結點集E1⊕

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

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

v0e1v1e2…elvlvv′若Pvv′不是基本路徑結點vi在該路徑中不止一次出現v0e1v1e2…eivi

ei+1

…

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

是可達的否則:從v1到v2不可達v1可達v2

在無向圖中:在有向圖中:v2可達v1

V2不一定可達v1

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

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

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

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

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

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

其中：

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

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

解答

由于圖中每個結點均為偶次數，故由定理可知這樣的一條清掃路線是存在的。

(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中結點vi與vj間存在歐拉路徑vi與vj的度數均為奇數其它結點的度數均為偶數定理應用舉例一筆畫問題：判別圖(1)、(2)是否可以一筆畫。解答圖(1)A、B為奇結點C,D,E為偶結點歐拉路徑:AEDCBECAB解答圖(2)A、B為奇結點其余各點為偶結點A與B兩點間存在歐拉路徑，即從A到B可以一筆畫。定理應用舉例判斷圖（3）是否可以一筆畫。A,B,C,D均為奇結點圖(3)中無歐拉路徑，因此不可以一筆畫。4、有向歐拉圖G:有向圖經過圖中每條邊一次且僅一次的有向路徑有向歐拉路徑:有向歐拉回路:經過圖中每條邊一次且僅一次的有向回路有向歐拉圖:有有向歐拉回路的有向圖定理

一個連通有向圖G是有向歐拉圖對G中的所有結點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、哈密頓圖的起源周游世界游戲： 從某個城市出發(fā)，經過每個城市一次且僅一次，最后回到出發(fā)點。2、哈密頓圖G:無向圖經過圖中每個結點一次且僅一次的路徑哈密頓路徑:哈密頓回路:經過圖中每個結點一次且僅一次的回路哈密頓圖:有哈密頓回路的圖哈密頓圖舉例

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

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

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

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

相鄰R4和R0

相鄰定理（歐拉公式）n-m+r=2G:連通的平面圖n:結點數m:邊數r:面數歐拉公式解釋

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

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

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

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

如果非連通無向圖G的每個分支都是樹，則稱G為森林。若森林的分支數為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不構成回路；②再取一條邊e3，使得e3和e1、e2不構成回路；③如此下去，最后得到的不含回路的連通生成子圖即是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條邊，結束。生成樹不唯一（2）破回路法（1）在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>:加權圖加權長度:所有邊的加權長度之和最小生成樹:G的所有生成樹中加權長度最小的生成樹7、求最小生成樹的算法（1）避回路法（2）破回路法（1）避回路法①選取權值最小的邊；②若m=n-1，則停止；否則③；③已選擇的邊為e1,e2,…,ei{e1,e2,…,ei,ei+1}中無回路ei+1:不同于e1,e2,…,ei的邊權值最小避回路法求最小生成樹舉例用避回路法求圖G的最小生成樹解答abcdef(1)選擇權值為1的邊(c,d);1(2)選擇權值為2的邊(b,f);2(3)選擇權值為3的邊(b,c);3(4)選擇權值為4的邊(a,b);4(5)權值為5的邊(a,f),形成回路,避開權值為6的邊(a,c),形成回路,避開;權值為7的邊(d,f),形成回路,避開;(6)選擇權值為8的邊(f,e);8加權長度＝1＋2＋3＋4＋8＝18最小生成樹（2）破回路法（1）在G中任取一個回路，去掉該回路中權值最大的一條邊，得到一個子圖G1；（2）在G1中再取一回路，再去掉該回路中權值最大的一條邊，得到一個子圖G2

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

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