圖論II圖的基本概念

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

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

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

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

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

6、.推論推論 在一個在一個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上的等價關(guān)系上的等價關(guān)系連通圖連通圖:任意兩點都連通的圖任意兩點都連通的圖. 平凡圖是連通圖平凡圖是連通圖.連通分支連通分支: V關(guān)于連通關(guān)系關(guān)于連通關(guān)系R的等價類的導(dǎo)出子圖的等價類的導(dǎo)出子圖設(shè)設(shè)V/R=V1,V2,Vk, GV1, GV2, ,

7、GVk是是G的連的連通分支通分支, 其個數(shù)記作其個數(shù)記作p(G)=k.G是連通圖是連通圖 p(G)=1例例9點割集點割集 記記 G v: 從從G中刪除中刪除v及關(guān)聯(lián)的邊及關(guān)聯(lián)的邊 G V : 從從G中刪除中刪除V 中所有的頂點及關(guān)聯(liá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的的點割集點割集. 若若v為點割集為點割集, 則稱則稱v為為割點割點.10點割集實例點割集實例例例 v1,v4, v6是點

8、割集是點割集, v6是割點是割點. v2,v5不是點割集不是點割集 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無點割集無點割集n階零圖既無點割集，也無邊割集階零圖既無點割集，也無邊割集.若若G連通，連通，E 為邊割集，則為邊割集，則p(G E

9、)=2若若G連通，連通，V 為點割集，則為點割集，則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強連通強連通: u,v V，u與與v相互可達(dá)相互可達(dá)強連通強連通單向連通單向連通弱連通弱連通 13有向圖的連通性有向圖的連通性( (續(xù)續(xù)) ) 定理定理(強連通判別法強連通判別法) D強連通當(dāng)且僅當(dāng)強連通當(dāng)且僅當(dāng)D中存在

10、經(jīng)中存在經(jīng)過每個頂點至少一次的回路過每個頂點至少一次的回路定理定理(單向連通判別法單向連通判別法) D單向連通當(dāng)且僅當(dāng)單向連通當(dāng)且僅當(dāng)D中存中存在經(jīng)過每個頂點至少一次的路在經(jī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的一種的一種點著點著色色,簡稱簡稱著色著色若能用若能用k種顏色給種顏色給G的頂點著色，的頂點著色， 則則稱稱G是是k-可著色可著色的的圖的著色問題圖的著色問題: 用盡可能少的顏色給圖著色用盡可能少的顏色給圖著色.16例例121222111111222322221111311122234例例例例2171122221112123213321232314例例例例3 學(xué)生會下設(shè)學(xué)生會下設(shè)6個委員會個委員會, 第一委員會第一委員會=張張, 李李, 王王, 第二委第二委員會員會=李李, 趙趙, 劉劉, 第三委員會第三委員會=張張, 劉劉, 王王, 第四委員會第四委員會=趙趙, 劉劉, 孫孫, 第五委員會第五委員會=張張, 王王, 第六委員會第六委員會=李