離散結(jié)構(gòu)課件6章圖論基礎(chǔ)

16.2圖的連通性6.2.1通路與回路初級(jí)通路(回路)與簡單通路(回路)6.2.2無向圖的連通性與連通度連通圖、連通分支短程線與距離點(diǎn)割集、割點(diǎn)、邊割集、割邊(橋)點(diǎn)連通度與邊連通度26.2圖的連通性(續(xù))6.2.3有向圖的連通性及其分類可達(dá)性弱連通、單向連通、強(qiáng)連通短程線與距離3通路與回路定義6.13給定圖G=<V,E>(無向或有向的),G中頂點(diǎn)與邊的交替序列=v0e1v1e2…elvl.若i(1il),ei=(vi1,vi)(對(duì)于有向圖,ei=<vi1,vi>,則稱為v0到vl的通路,v0和vl分別為通路的起點(diǎn)和終點(diǎn),l為通路的長度.又若v0=vl,則稱為回路.若通路(回路)中所有頂點(diǎn)(對(duì)于回路,除v0=vl)各異,則稱為初級(jí)通路或路徑(初級(jí)回路或圈).長度為奇數(shù)的圈稱作奇圈,長度為偶數(shù)的圈稱作偶圈若通路(回路)中所有邊各異,則稱為簡單通路(簡單回路),否則稱為復(fù)雜通路(復(fù)雜回路)4說明(1)初級(jí)通路(回路)是簡單通路(回路),但反之不真初級(jí)通路非初級(jí)的簡單通路初級(jí)回路非初級(jí)的簡單回路5說明(2)表示方法①按定義用頂點(diǎn)和邊的交替序列,=v0e1v1e2…elvl②用邊序列,=e1e2…el③簡單圖中,用頂點(diǎn)序列,=v0v1…vl(3)在無向圖中,長度為1的圈由環(huán)構(gòu)成.長度為2的圈由兩條平行邊構(gòu)成.在無向簡單圖中,所有圈的長度3.在有向圖中,長度為1的圈由環(huán)構(gòu)成.在有向簡單圖中,所有圈的長度2.6通路與回路(續(xù))定理6.3在n階圖中,若從頂點(diǎn)u到v(uvj)存在通路,則從u到v存在長度小于等于n1的初級(jí)通路.證若通路中沒有相同的頂點(diǎn)(即初級(jí)通路),長度必n1.若有相同的頂點(diǎn),刪去這兩個(gè)頂點(diǎn)之間的這一段,仍是u到v的通路.重復(fù)進(jìn)行,直到?jīng)]有相同的頂點(diǎn)為止.定理6.4

在n階圖中,若存在v到自身的簡單回路,則一定存在v到自身長度小于等于n的初級(jí)回路.7無向圖的連通性與連通分支設(shè)無向圖G=<V,E>,u,vVu與v連通:若u與v之間有通路.規(guī)定u與自身總是連通的.連通圖:任意兩點(diǎn)都連通的圖.平凡圖是連通圖連通關(guān)系R={<u,v>|u,vV且u與v連通}.R是等價(jià)關(guān)系連通分支:V關(guān)于R的等價(jià)類的導(dǎo)出子圖設(shè)V/R={V1,V2,…,Vk},G的連通分支為G[V1],G[V2],…,G[Vk]連通分支數(shù)p(G)=kG是連通圖

p(G)=18短程線與距離u與v之間的短程線:u與v之間長度最短的通路(設(shè)u與v連通)u與v之間的距離d(u,v):u與v之間短程線的長度若u與v不連通,規(guī)定d(u,v)=∞.性質(zhì)：(1)

d(u,v)0,且d(u,v)=0

u=v(2)d(u,v)=d(v,u)(3)d(u,v)+d(v,w)d(u,w)

例如a與e之間的短程線:ace,afe.d(a,e)=2,d(a,h)=∞abcdefghi9點(diǎn)割集與邊割集設(shè)無向圖G=<V,E>,vV,eE,VV,E

E.記Gv:從G中刪除v及關(guān)聯(lián)的邊GV

:從G中刪除V

中所有的頂點(diǎn)及關(guān)聯(lián)的邊Ge:從G中刪除eGE

:從G中刪除E

中所有邊定義6.15設(shè)無向圖G=<V,E>,V

V,若p(GV

)>p(G)且VV

,p(GV

)=p(G),則稱V

為G的點(diǎn)割集.若{v}為點(diǎn)割集,則稱v為割點(diǎn).設(shè)E

E,若p(GE

)>p(G)且E

E

,p(GE

)=p(G),則稱E

為G的邊割集.若{e}為邊割集,則稱e為割邊或橋.10實(shí)例說明：Kn無點(diǎn)割集n階零圖既無點(diǎn)割集，也無邊割集.若G連通，E

為邊割集，則p(GE

)=2若G連通，V

為點(diǎn)割集，則p(GV

)2abcdefge1e2e3e4e5e6e7e8e9e,f點(diǎn)割集:{e},{f},割點(diǎn):{c,d}

橋:e8,e9邊割集:{e8},{e9},{e1,e2},{e1,e3,e6},{e1,e3,e4,e7}11點(diǎn)連通度與邊連通度定義6.16設(shè)無向連通圖G=<V,E>,(G)=min{|V||V是G的點(diǎn)割集或使GV成為平凡圖}

稱(G)為G的點(diǎn)連通度(G)=min{|E||E是G的邊割集}稱(G)為G的邊連通度例如3(G)=3(G)=12點(diǎn)連通度與邊連通度(續(xù))說明:(1)若G是平凡圖,則(G)=0,(G)=0.(2)若G是完全圖Kn,則(G)=n1,(G)=n1(3)若G中存在割點(diǎn),則(G)=1;若G中存在割邊,則

(G)=1(4)規(guī)定非連通圖的點(diǎn)連通度和邊連通度均為0定理6.5對(duì)任何無向圖G,有

(G)(G)(G)13有向圖的連通性及其分類設(shè)有向圖D=<V,E>,u,vV,u可達(dá)v:u到v有通路.規(guī)定u到自身總是可達(dá)的.u與v相互可達(dá):u可達(dá)v且v可達(dá)uD弱連通(連通):略去各邊的方向所得無向圖為連通圖D單向連通:u,vV，u可達(dá)v

或v可達(dá)u

D強(qiáng)連通:u,vV，u與v相互可達(dá)D是強(qiáng)連通的當(dāng)且僅當(dāng)D中存在經(jīng)過所有頂點(diǎn)的回路D是單向連通的當(dāng)且僅當(dāng)D中存在經(jīng)過所有頂點(diǎn)的通路14實(shí)例

強(qiáng)連通單連通弱連通15有向圖中的短程線與距離u到v的短程線:u到v長度最短的通路(設(shè)u可達(dá)