圖論II圖的基本概念

1、11.2 路、回路、圖的連通性路、回路、圖的連通性 路路,通路通路,跡跡無向圖的連通性無向圖的連通性 無向連通圖無向連通圖, 連通分支連通分支有向連通圖有向連通圖 弱連通圖弱連通圖, 單向連通圖單向連通圖, 強(qiáng)連通圖強(qiáng)連通圖點(diǎn)割集與割點(diǎn)點(diǎn)割集與割點(diǎn)邊割集與割邊邊割集與割邊(橋橋) 2路與回路路與回路 定義定義 給定圖給定圖G=（無向或有向的），（無向或有向的），G中頂點(diǎn)與邊的交中頂點(diǎn)與邊的交替序列替序列 =v0e1v1e2elvl，(1) 若若 i(1 i l), vi 1, vi是是ei的端點(diǎn)的端點(diǎn)(對于有向圖對于有向圖, 要求要求vi 1是始點(diǎn)是始點(diǎn), vi是終點(diǎn)是終點(diǎn)), 則稱則稱 為為

2、路路, v0是是路的起點(diǎn)路的起點(diǎn), vl是是路的終點(diǎn)路的終點(diǎn), l為為路的路的長度長度. 又若又若v0=vl，則稱，則稱 為為回路回路.(2) 若路若路(回路回路)中所有頂點(diǎn)中所有頂點(diǎn)(對于回路對于回路, 允許允許v0=vl)各異，則稱為各異，則稱為通路通路(圈圈). (3) 若路若路(回路回路)中所有邊各異中所有邊各異, 則稱為則稱為跡跡(閉跡閉跡).路中不含重復(fù)頂點(diǎn)，則一定不含重復(fù)邊。通路一定是跡。路中不含重復(fù)頂點(diǎn)，則一定不含重復(fù)邊。通路一定是跡。按通暢性要求由高到低：按通暢性要求由高到低： 通路通路 跡跡 路路按可能的復(fù)雜或曲折程度由高到低：路按可能的復(fù)雜或曲折程度由高到低：路 跡跡 通

3、路通路路與回路路與回路n試分別畫出：一條通路一條非通路的跡一條非跡的路從中直觀感受一下路、跡和通路對通暢程度的不同要求路與回路實(shí)例路與回路實(shí)例45路與回路路與回路( (續(xù)續(xù)) )說明說明:n表示方法表示方法 用頂點(diǎn)和邊的交替序列用頂點(diǎn)和邊的交替序列(定義定義), 如如 =v0e1v1e2elvl 用邊的序列用邊的序列, 如如 =e1e2el 簡單圖中簡單圖中, 用頂點(diǎn)的序列用頂點(diǎn)的序列, 如如 =v0v1vl 非簡單圖中非簡單圖中,可用混合表示法可用混合表示法,如如 =v0v1e2v2e5v3v4v5n環(huán)是長度為環(huán)是長度為1的圈的圈, 兩條平行邊構(gòu)成長度為兩條平行邊構(gòu)成長度為2的圈的圈.n在無

4、向簡單圖中在無向簡單圖中, 所有圈的長度所有圈的長度 3; 在有向簡單圖在有向簡單圖中中, 所有圈的長度所有圈的長度 2. 6路與回路路與回路( (續(xù)續(xù)) )n在兩種意義下計(jì)算圈的個(gè)數(shù)在兩種意義下計(jì)算圈的個(gè)數(shù) 定義意義下定義意義下 在無向圖中在無向圖中, 一個(gè)長度為一個(gè)長度為l(l 3)的圈看作的圈看作2l個(gè)不同的個(gè)不同的圈圈. 如如v0v1v2v0 , v1v2v0v1 , v2v0v1v2, v0v2v1v0 , v1v0v2v1 , v2v1v0v2看作看作6個(gè)不同的圈個(gè)不同的圈. 在有向圖中在有向圖中, 一個(gè)長度為一個(gè)長度為l(l 3)的圈看作的圈看作l個(gè)不同的個(gè)不同的圈圈. 同構(gòu)意義

5、下同構(gòu)意義下 所有長度相同的圈都是同構(gòu)的所有長度相同的圈都是同構(gòu)的, 因而是因而是1個(gè)圈個(gè)圈. 7路與回路路與回路( (續(xù)續(xù)) ) 定理定理 在在n階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)u到到v（u v）存在通）存在通路，則從路，則從u到到v存在長度小于等于存在長度小于等于n 1的路的路.推論推論 在在n階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)u到到v（u v）存在通）存在通路，則從路，則從u到到v存在長度小于等于存在長度小于等于n 1的通路的通路.定理定理 在一個(gè)在一個(gè)n階圖階圖G中，若存在中，若存在v到自身的回路，則到自身的回路，則一定存在一定存在v到自身長度小于等于到自身長度小于等于n的回路的回路

6、.推論推論 在一個(gè)在一個(gè)n階圖階圖G中，若存在中，若存在v到自身的回路，則到自身的回路，則存在存在v到自身長度小于等于到自身長度小于等于n的圈的圈. 8無向圖的連通性無向圖的連通性 設(shè)無向圖設(shè)無向圖G=,u與與v連通連通: u與與v間有路，記為間有路，記為u v. 規(guī)定規(guī)定u與自身總連與自身總連通通.連通關(guān)系連通關(guān)系 R=| u,v V且且u v是是V上的等價(jià)關(guān)系上的等價(jià)關(guān)系連通圖連通圖:任意兩點(diǎn)都連通的圖任意兩點(diǎn)都連通的圖. 平凡圖是連通圖平凡圖是連通圖.連通分支連通分支: V關(guān)于連通關(guān)系關(guān)于連通關(guān)系R的等價(jià)類的導(dǎo)出子圖的等價(jià)類的導(dǎo)出子圖設(shè)設(shè)V/R=V1,V2,Vk, GV1, GV2, ,

7、GVk是是G的連的連通分支通分支, 其個(gè)數(shù)記作其個(gè)數(shù)記作p(G)=k.G是連通圖是連通圖 p(G)=1例例9點(diǎn)割集點(diǎn)割集 記記 G v: 從從G中刪除中刪除v及關(guān)聯(lián)的邊及關(guān)聯(lián)的邊 G V : 從從G中刪除中刪除V 中所有的頂點(diǎn)及關(guān)聯(lián)的邊中所有的頂點(diǎn)及關(guān)聯(lián)的邊 G e : 從從G中刪除中刪除e G E : 從從G中刪除中刪除E 中所有邊中所有邊定義定義 設(shè)無向圖設(shè)無向圖G=, V V, 若若p(G V )p(G)且且 V V , p(G V )=p(G), 則稱則稱V 為為G的的點(diǎn)割集點(diǎn)割集. 若若v為點(diǎn)割集為點(diǎn)割集, 則稱則稱v為為割點(diǎn)割點(diǎn).10點(diǎn)割集實(shí)例點(diǎn)割集實(shí)例例例 v1,v4, v6是點(diǎn)

8、割集是點(diǎn)割集, v6是割點(diǎn)是割點(diǎn). v2,v5不是點(diǎn)割集不是點(diǎn)割集 11邊割集邊割集定義定義 設(shè)無向圖設(shè)無向圖G=, E E, 若若p(G E )p(G)且且 E E , p(G E )=p(G), 則稱則稱E 為為G的的邊割集邊割集. 若若e為邊割集為邊割集, 則稱則稱e為為割邊割邊或或橋橋.在上一頁的圖中，在上一頁的圖中，e1,e2，e1,e3,e5,e6，e8等是邊割集，等是邊割集，e8是橋，是橋，e7,e9,e5,e6不是邊割集不是邊割集說明：說明：Kn無點(diǎn)割集無點(diǎn)割集n階零圖既無點(diǎn)割集，也無邊割集階零圖既無點(diǎn)割集，也無邊割集.若若G連通，連通，E 為邊割集，則為邊割集，則p(G E

9、)=2若若G連通，連通，V 為點(diǎn)割集，則為點(diǎn)割集，則p(G V ) 2 12有向圖的連通性有向圖的連通性 設(shè)有向圖設(shè)有向圖D=u可達(dá)可達(dá)v: u到到v有路有路. 規(guī)定規(guī)定u到自身總是可達(dá)的到自身總是可達(dá)的.可達(dá)具有自反性和傳遞性可達(dá)具有自反性和傳遞性D弱連通弱連通(連通連通): 基圖為無向連通圖基圖為無向連通圖D單向連通單向連通: u,v V，u可達(dá)可達(dá)v 或或v可達(dá)可達(dá)u D強(qiáng)連通強(qiáng)連通: u,v V，u與與v相互可達(dá)相互可達(dá)強(qiáng)連通強(qiáng)連通單向連通單向連通弱連通弱連通 13有向圖的連通性有向圖的連通性( (續(xù)續(xù)) ) 定理定理(強(qiáng)連通判別法強(qiáng)連通判別法) D強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)D中存在

10、經(jīng)中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路過每個(gè)頂點(diǎn)至少一次的回路定理定理(單向連通判別法單向連通判別法) D單向連通當(dāng)且僅當(dāng)單向連通當(dāng)且僅當(dāng)D中存中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的路在經(jīng)過每個(gè)頂點(diǎn)至少一次的路 例例 強(qiáng)連通強(qiáng)連通單向連通單向連通弱連通弱連通141.3 帶權(quán)圖、最短路徑、圖著色帶權(quán)圖、最短路徑、圖著色n帶權(quán)圖與最短路徑帶權(quán)圖與最短路徑n圖著色問題圖著色問題15最短路徑最短路徑帶權(quán)圖帶權(quán)圖G=, 其中其中w:ER. e E, w(e)稱作稱作e的的權(quán)權(quán). 若若e=(vi,vj), 記記w(e)=wij . 若若vi,vj不相鄰不相鄰, 記記wij = . 路路L的的權(quán)權(quán): L的所有邊的權(quán)之和的

11、所有邊的權(quán)之和, 記作記作w(L).u和和v之間的之間的最短路徑最短路徑: u和和v之間權(quán)最小的路之間權(quán)最小的路.例例 L1=v0v1v3v5, w(L1)=10, L2=v0v1v4v5, w(L2)=12, L3=v0v2v4v5, w(L3)=11.著色著色定義定義 設(shè)無向圖設(shè)無向圖G無環(huán)無環(huán), 對對G的每個(gè)頂點(diǎn)涂一種顏色，的每個(gè)頂點(diǎn)涂一種顏色，使相鄰的頂點(diǎn)涂不同的顏色，稱為圖使相鄰的頂點(diǎn)涂不同的顏色，稱為圖G的一種的一種點(diǎn)著點(diǎn)著色色,簡稱簡稱著色著色若能用若能用k種顏色給種顏色給G的頂點(diǎn)著色，的頂點(diǎn)著色， 則則稱稱G是是k-可著色可著色的的圖的著色問題圖的著色問題: 用盡可能少的顏色給圖著色用盡可能少的顏色給圖著色.16例例121222111111222322221111311122234例例例例2171122221112123213321232314例例例例3 學(xué)生會(huì)下設(shè)學(xué)生會(huì)下設(shè)6個(gè)委員會(huì)個(gè)委員會(huì), 第一委員會(huì)第一委員會(huì)=張張, 李李, 王王, 第二委第二委員會(huì)員會(huì)=李李, 趙趙, 劉劉, 第三委員會(huì)第三委員會(huì)=張張, 劉劉, 王王, 第四委員會(huì)第四委員會(huì)=趙趙, 劉劉, 孫孫, 第五委員會(huì)第五委員會(huì)=張張, 王王, 第六委員會(huì)第六委員會(huì)=李