集合論與圖論第七章

集合論與圖論第七章第一頁(yè)，共四十五頁(yè)，編輯于2023年，星期五17.1樹及其性質(zhì)僅有一個(gè)頂點(diǎn)的樹稱為平凡樹。定義7.1.1連通且無(wú)圈的無(wú)向圖稱為無(wú)向樹,簡(jiǎn)稱樹。一個(gè)沒(méi)有圈的不連通的無(wú)向圖稱為無(wú)向森林,簡(jiǎn)稱森林;第二頁(yè)，共四十五頁(yè)，編輯于2023年，星期五2

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

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

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

v4v3v2

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

v4v2v5

v3v8v9v1v6v7

v4v2

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