集合論與圖論第七章

集合論與圖論第七章第一頁，共四十五頁，編輯于2023年，星期五17.1樹及其性質僅有一個頂點的樹稱為平凡樹。定義7.1.1連通且無圈的無向圖稱為無向樹,簡稱樹。一個沒有圈的不連通的無向圖稱為無向森林,簡稱森林;第二頁，共四十五頁，編輯于2023年，星期五2

定理7.1.1設G=(V,E)是一個(p,q)圖,則下列各命題等價:(1)G是樹(2)G的任意兩個不同頂點間有唯一的一條路聯(lián)結;(3)G是連通的且p=q+1;(4)G中無圈且p=q+1;

(5)G中無圈且G中任意兩個不鄰接的頂點間加一條邊,則得到一個有唯一的一個圈的圖;

(6)G是連通的,并且若p≥3,則G不是Kp,G中任意兩個不鄰接的頂點間加一條邊,則得到一個有唯一的一個圈的圖。7.1樹及其性質第三頁，共四十五頁，編輯于2023年，星期五3推論7.1.1任一非平凡樹中至少有兩個度為1的頂點。7.1樹及其性質定義7.1.2連通圖G稱為是極小連通圖,如果去掉G的任意一條邊后得到的都是不連通圖。極小連通圖推論7.1.2圖G是樹當且僅當G是極小連通圖。第四頁，共四十五頁，編輯于2023年，星期五4定義7.1.3設G=(V,E)是連通圖,vV,數(shù)稱為v在G中的偏心率,vv點的偏心率是3,頂點v的偏心率7.1樹及其性質連通圖G的半徑稱為G的半徑,滿足r(G)=e(v)的頂點v稱為G的中心點,G的所有中心點組成的集合稱為G的中心,G的中心記為C(G)第五頁，共四十五頁，編輯于2023年，星期五5定理7.1.2每棵樹的中心或含有一個頂點,或含有兩個鄰接的頂點v4v5v3v2v1離中心最遠的點滿足什么性質?都是一度頂點;

v4v3v2

如果把1度頂點都去掉，會不會引起中心點的變化？不會引起中心點的變化。7.1樹及其性質圖1圖2圖3v5v6v4v3v2v1第六頁，共四十五頁，編輯于2023年，星期五6定理7.1.2每棵樹的中心或含有一個頂點,或含有兩個鄰接的頂點。[證]顯然,一個頂點的樹有一個中心,兩個頂點的樹有兩個中心,這時定理成立;設v是中心,則v只有到達一個一度頂點時,其偏心率才能達到最大值。把所有的一度頂點全去掉，則其中心的偏心率都少1。每次把所有的一度頂點全去掉，并不引起中心的變化。每次把所有的一度頂點全去掉,經有限步必可得到一個只有一個頂點的樹,或只有兩個頂點的樹。7.1樹及其性質第七頁，共四十五頁，編輯于2023年，星期五7例7.1.1任何一個非平凡的樹都可用兩種顏色給其頂點染色,使得每條邊的兩個端點不同色。由第六章第4節(jié)中偶圖的充分必要條件是圖中所有圈都是偶數(shù)長可得樹是偶圖。因此樹可用兩種顏色染色，并且每條邊的兩個端點不同色。7.1樹及其性質第八頁，共四十五頁，編輯于2023年，星期五87.2生成樹1、若圖G有生成樹,則G是連通的,所以不連通圖沒有生成樹,定義7.2.1設G=(V,E)是一個圖,G的一個生成子圖T=(V,F)如果是樹,則稱T是G的生成樹。2、連通圖都有生成樹嗎?定理7.2.1圖G有生成樹的充分必要條件是G為一個連通圖。第九頁，共四十五頁，編輯于2023年，星期五9推論7.2.1設G是一個(p,q)連通圖,則q≥p-1。定義7.2.2設G是一個圖,若G的生成子圖F是一個森林,則F稱為G的一個生成森林。任意圖都有生成森林。7.2生成樹第十頁，共四十五頁，編輯于2023年，星期五10定理7.2.2具有p個頂點的完全圖Kp有pp-2棵生成樹,p≥2.[證]設Kp的頂點集V={1,2,...,p},定理中的數(shù)pp-2恰好是以V中數(shù)為項的長為p-2的所有序列的個數(shù),要證明該定理,只須在Kp的所有生成樹之集與這些長為p-2的序列之集間建立一個一一對應即可。7.2生成樹第十一頁，共四十五頁，編輯于2023年，星期五1112534設一棵樹的頂點集為A1、從中找到編號最小的葉子結點，去掉該葉子結點a1及其鄰接邊(a1,b1)。2、重復以上過程。只到剩一條邊為止。(1,2),(4,3),(3,2)這棵樹對應序列（2，3，2）一個棵對應序列B=b1b2b3…bp-2而且是唯一的定理7.2.2具有p個頂點的完全圖Kp有pp-2棵生成樹,p≥2.7.2生成樹第十二頁，共四十五頁，編輯于2023年，星期五1212534樹的頂點集合為12345這棵樹對應序列（2，3，2）任給一個序列B{b1,b2,b3,…,bp-2}1、從A找到最小的不屬于B的元素,設為a1,與b1連接，從A中去掉a1，從B中去掉b1.2、重復以上過程只到B為空，A中剩余兩個3、連接剩余的兩個頂點。7.2生成樹第十三頁，共四十五頁，編輯于2023年，星期五13定理7.2.3設G=(V,E)是連通圖,T1=(V,E1)和T2=(V,E2)是G的兩個不同的生成樹,如果e1E1\E2,則e2E2\E1,使得(T1-e1)+e2為G的一棵生成樹。7.2生成樹[證]所以(T1-e1)+e2是G的生成樹。由于T2是連通的，所以必然在V1與V2之間存在T2的一條邊e2，因為V1與V2之間在T1中只有一條邊e1，所以e2E1,由樹的性質,T1-e1恰有兩個支,設這兩支分別為G1=(V1,F1),G2=(V2,F2)因為e1E2,所以e2≠e1第十四頁，共四十五頁，編輯于2023年，星期五14定義7.2.3設T1,T2是G的生成樹,是T1的邊但不是T2的邊的條數(shù)k稱為T1與T2的距離,記為d(T1,T2)=k。由定義可知d(T1,T2)≥0,G的生成樹之間的距離并且d(T2,T1)=d(T1,T2)設T1的邊集為E1,T2的邊集為E2,用集合怎么表示兩個生成樹之間的距離?E1\E27.2生成樹第十五頁，共四十五頁，編輯于2023年，星期五15d(T1,T2)≤d(T1,T3)+d(T3,T2)是T1的邊但不是T2的邊包括在如下情況中,是T1的邊不是T2的邊是T3的邊,是T1的邊不是T2的邊也不是T3的邊,7.2生成樹第十六頁，共四十五頁，編輯于2023年，星期五16兩個生成樹之間的基本樹變換若d(T1,T2)=1,T2=(T1-e1)+e2它稱為從T1到T2的一個基本樹變換。則T1中有一條邊e1不在T2中,T2中也有一條邊不在T1中,7.2生成樹第十七頁，共四十五頁，編輯于2023年，星期五17定理7.2.4設T0和T是G的兩距離為k的生成樹,則從T0開始經k次基本樹變換便可得到T。當k=0成立;[證]假設k≤n時結論成立,需證k=n+1時定理成立,設d(T0,T)=n+1,當k=1時，由定理7.2.3知結論成立。由定理7.2.3,從T0中去掉一條不在T中邊e1后,必在T中找到一條不在T0中邊e27.2生成樹第十八頁，共四十五頁，編輯于2023年，星期五18d(T1,T)=n,由假設知d(T0,T)=n+1,由歸納假設,從T1經n個基本樹變換便到T,因此從T0經n+1個基本樹變換得到T因此定理成立。使得(T0-e1)+e2為生成樹,設(T0-e1)+e2=T1,7.2生成樹第十九頁，共四十五頁，編輯于2023年，星期五19最小生成樹問題生成樹的權圖G123123T1231237.2生成樹給定邊帶權連通圖G,G中邊的權是一個非負實數(shù),生成樹中各邊的權之和稱為該生成樹的權；G的生成樹中權最小的那個生成樹就是最小生成樹。圖G的生成樹T的權是6第二十頁，共四十五頁，編輯于2023年，星期五20如果邊的權代表路程，最小生成樹就是原圖中路程最短的連通圖。如果邊的權代表修路資金，最小生成樹就是原圖中花費資金最少的連通圖。1、最小生成樹不一定只有一個；2、最小生成樹按邊的權的性質不同可以有不同的理解；7.2生成樹第二十一頁，共四十五頁，編輯于2023年，星期五21定義7.2.4設T是連通圖G的生成樹,G中不是T的邊稱為T的弦。若G是一個(p,q)連通圖,T是G的生成樹,問T有多少條弦?T有p-1條邊,有q-p+1條弦,生成樹T的弦生成樹T的基本圈,如果e是T的一條弦,則T+e中有唯一的一個圈,這個圈稱為G的相對生成樹T的基本圈,在這個圈上只有e是T的弦,其它都是T的邊,7.2生成樹第二十二頁，共四十五頁，編輯于2023年，星期五22設G=(V,E,w)是一個邊帶權圖,其中對每條邊xE,w(x)>0,如果T0是G的一個最小生成樹,e是T0的一條弦,則T0+e中有唯一的一個圈C,C上的每條邊x有w(x)≤w(e)G12433w(e)如果有一條邊x,w(x)>w(e)從圈中去掉邊x,加入邊e則得到一個比T0更小的生成樹。G12433w(e)7.2生成樹第二十三頁，共四十五頁，編輯于2023年，星期五23定理7.2.5設G=(V,E,w)是一個連通的邊帶權圖,邊上的權函數(shù)w是非負,{(V1,E1),(V2,E2),...,(Vk,Ek)}是G的生成森林,k>1,F=,如果e=uv是E\F中權值最小的邊且uV1,vV1中,則存在G的一個包含F(xiàn)∪{e}的生成樹T,使得T的權不大于任一包含F(xiàn)的生成樹的權。7.2生成樹第二十四頁，共四十五頁，編輯于2023年，星期五24生成樹T123344uve圖G123344uve生成樹T的權是包含生成森林的生成樹中權最小的生成樹。7.2生成樹第二十五頁，共四十五頁，編輯于2023年，星期五25[證]用反證法證明把e加到T中,則T+e中有唯一的圈C使得C上除了邊e外,必還有邊e=uv,uV1,vV1,根據(jù)e的假設必有w(e)≤w(e),從T+e中去掉e,得到一生成樹T,T包含了F∪{e},并且T的權不大于T的權,這與關于T的假定相矛盾;如若不然,則G有一個生成樹T=(V,E),T包含F(xiàn)(即FE),不包含邊e；T的權小于任一包含F(xiàn)∪{e}的生成樹的權,因此定理成立。7.2生成樹第二十六頁，共四十五頁，編輯于2023年，星期五26最小生成樹Kruskal算法1453026515735642145302∞∞∞∞∞∞7.2生成樹第二十七頁，共四十五頁，編輯于2023年，星期五277.2生成樹輸入:連通圖G=(V,E),其中V={1,2,…,n},輸出:一顆最小生成樹:算法:voidKruskal(V,T){T=V;ncomp=n;//連通分支while(ncomp>1){從E中取出刪除權最小的邊(v,u);if(v和u屬于T中不同的連通分支){T=T∪{(v,u)};ncomp--;}}}第二十八頁，共四十五頁，編輯于2023年，星期五28定理7.2.6設G=(V,E,w)是一個邊帶權連通圖,U是V的一個真子集,如果{u,v}是uU,vV\U的G的一條邊,并且是所有的這樣的邊中,{u,v}的權w(u,v)最小,則G中一定存在一個最小生成樹,它以{u,v}為其中一條邊。7.2生成樹abcdefg1818191520820931516UV\U第二十九頁，共四十五頁，編輯于2023年，星期五29[證]用反證法于是,T是含邊{u,v}的最小生成樹;在圈上有一條邊{u,v},使得uU,vV\U;假如G的最小生成樹都不含邊{u,v};令T=(T+uv)-uv,由于w(u,v)≤w(u,v),所以T的權≤T的權;這與假設相矛盾。把邊{u,v}加到G的一棵最小生成樹T中,那么T+uv中有一個含邊uv的圈;7.2生成樹第三十頁，共四十五頁，編輯于2023年，星期五30Prim算法的基本思想是:1、先置U={i1},E={},選取滿足i2V\U的邊{i1,i2}使w(i1,i2)最小;直到把所有的頂點都加入到U中,所得到的邊集就構成一棵最小生成樹。設G=(V,E,w)是帶權連通圖,V={1,2,...,p}2、置U={i1,i2},E={i1i2},選取滿足iU,i3V\U的邊{i,i3},使w(i,i3)最小;3、置U={i1,i2,i3},E={i1i2,ii3},繼續(xù)這樣的過程;7.2生成樹**第三十一頁，共四十五頁，編輯于2023年，星期五317.3割點、橋和割集定義7.3.1設v是圖G的一個頂點，如果G-v的支數(shù)大于G的支數(shù)，則稱頂點v為圖G的一個割點。上圖中v5是割點，其它都不是割點。1、割點v1v6v7

v4v2v5

v3v8v9v1v6v7

v4v2

v3v8v9第三十二頁，共四十五頁，編輯于2023年，星期五32定義7.3.2圖G的一條邊x稱為G的一座橋，如果G-x的支數(shù)大于G的支數(shù)。圖中邊v2v5是橋；2、橋v1v6v4v2v5v7v3圖中邊v5v6,v5v7也是橋。7.3割點、橋和割集第三十三頁，共四十五頁，編輯于2023年，星期五33定理7.3.1設v是連通圖G=(V,E)的一個頂點，則下列命題等價：(1)v是圖G的一個割點;(2)存在與v不同的兩個頂點u和w,使得v在每一條u與w間的路上;(3)集合V\{v}有一個二劃分{U,W}使得uU,wW,v在聯(lián)結u和w的每條路上。7.3割點、橋和割集第三十四頁，共四十五頁，編輯于2023年，星期五34定理7.3.2每個非平凡的連通圖至少有兩個頂點不是割點。[證]非平凡圖的連通圖必有生成樹,非平凡樹至少有兩個度為1的頂點,它們就是原圖的非割點。7.3割點、橋和割集第三十五頁，共四十五頁，編輯于2023年，星期五35定理7.3.3設x是連通圖G=(V,E)的一條邊,則下列命題等價。(1)x是G的橋;(2)x不在G的任一圈上;(3)存在G的兩個不同頂點u和v,使得邊x在聯(lián)結u和v的每條路上;(4)存在V的一個劃分{U,W},使得uU及wW,x在每一條連接u與w的路上。7.3割點、橋和割集第三十六頁，共四十五頁，編輯于2023年，星期五36定義7.3.3圖G=(V,E),SE,如果從G中去掉S中的所有邊得到的圖G-S的支數(shù)大于G的支數(shù),而去掉S的任一真子集中的邊得到的圖的支數(shù)不大于G的支數(shù),則稱S為G的一個割集。割集7.3割點、橋和割集abcdefg1818191520820931516第三十七頁，共四十五頁，編輯于2023年，星期五37定理7.3.4設S是連通圖G=(V,E)的割集,則G-S恰有兩個支。[證]這與S是割集矛盾,所以G-S恰有兩個支。假如G-S的支數(shù)大于2,則把S的邊逐一加入G-S中；每加入一條邊至多能把G-S的兩個支聯(lián)結在一起；將G中邊逐一加入G-S中,總有一步使之有兩個支;設加入的邊為{x1,x2,...,xn}；則S1=S-{x1,x2,...,xn}是S的一個真子集；G-S1的支數(shù)也比G的支數(shù)多；7.3割點、橋和割集第三十八頁，共四十五頁，編輯于2023年，星期五38推論7.3.2不連通圖G的每個割集必是G的某個支的割集。推論7.3.1設G是一個有k個支的圖,如果S是G的割集,則G-S恰有k+1個支。7.3割點、橋和割集定理7.3.5設T是連通圖G=(V,E)的任一生成樹,則G的每個割集至少包含T的一條邊。第三十九頁，共四十五頁，編輯于2023年，星期五39定理7.3.6連通圖G的每個圈與G的任一割集有偶數(shù)條公共邊。[證]設C是連通圖G中的一個圈,S是G的一個割集,G1和G2是G-S的僅有的兩個支,如果C在G1中或G2中,則C與S無公共邊,所以公共邊數(shù)為0,故這時定理的結論成立,7.3割點、橋和割集第四十頁，共四十五頁，編輯于2023年，星期五40現(xiàn)在假設圈C與割集S有公共邊,則C上既有G1的頂點又有G2的頂點,當從G1的一個頂點v1開始沿C周游時,必經一條邊其兩端分別在G1和G2里,然后在某個時候又經過另一條這樣的邊返回G1,如此走下去,當走完圈的邊而回到v1時經過偶數(shù)次這樣的邊，兩個端點分別在G1與G2中,這樣的邊必在S中,所以,這時C與S也有偶數(shù)條邊。7.3割點、橋和割集第四十一頁，共四十五頁，編輯于2023年，星期五41設G=(V,E)是一個連通圖,T=(V,F)是G的一個生成樹。T+e中的唯一圈稱為G的相對于生成樹T的基本圈,這些基本圈之集稱為與T關聯(lián)的基本圈系統(tǒng)。弦與基本圈E\F中的每條邊e為T的弦,T+e中有唯一的一個圈,7.3割點、橋和割集v1v6v4