離散件圖的道路與連通

離散件圖的道路與連通演示文稿現(xiàn)在是1頁(yè)\一共有38頁(yè)\編輯于星期日（優(yōu)選）離散件圖的道路與連通現(xiàn)在是2頁(yè)\一共有38頁(yè)\編輯于星期日2。道路的分類：①跡：任何滿足道路定義的道路。②簡(jiǎn)單道路：邊不重復(fù)出現(xiàn)的道路。③基本道路：結(jié)點(diǎn)不重復(fù)出現(xiàn)的道路。例：上圖中，p1是跡，p2是簡(jiǎn)單道路，p3是基本道路，p4是零道路?，F(xiàn)在是3頁(yè)\一共有38頁(yè)\編輯于星期日3?；芈罚浩瘘c(diǎn)和終點(diǎn)相同的道路。邊不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路。結(jié)點(diǎn)不重復(fù)出現(xiàn)的回路稱為圈。例：下圖中，c1是一般回路，c2是簡(jiǎn)單回路，c3是圈。現(xiàn)在是4頁(yè)\一共有38頁(yè)\編輯于星期日例：下圖中c1=v1e1v1e2v2e7v4e8v3e4v1e3v2e2v1c2=v1e1v1e2v2e3v1e5v4e8v3e4v1c3=v1e5v4e10v6e12v5e9v3e4v1（c3可簡(jiǎn)記為：c3=v1v4v6v5v3v1）都是回路。c1是一般回路，c2是簡(jiǎn)單回路，c3是圈。v1v2v3v4v6v5e9e10e12e8e7e2e4e5e6e3e1e11現(xiàn)在是5頁(yè)\一共有38頁(yè)\編輯于星期日4。定理：設(shè)G是n階圖，如果存在從結(jié)點(diǎn)u到v的道路，則必存在長(zhǎng)度不超過(guò)n-1的道路。

證明要點(diǎn)：如果結(jié)點(diǎn)u到v的道路p的長(zhǎng)度超過(guò)n-1，則p中至少有n+1個(gè)結(jié)點(diǎn)，因而道路中至少有一個(gè)結(jié)點(diǎn)出現(xiàn)兩次，如viei...v1，則去掉ei...vi后仍是結(jié)點(diǎn)u到v的道路，但是道路長(zhǎng)度至少短1。重復(fù)這一過(guò)程，即得所需結(jié)論。現(xiàn)在是6頁(yè)\一共有38頁(yè)\編輯于星期日二、無(wú)向圖的連通問(wèn)題1。定義:如果存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的道路，則稱u到v是連通的。結(jié)點(diǎn)集V上的“連通”關(guān)系具有性質(zhì)：自反、對(duì)稱、傳遞。2。如果圖G中任何兩個(gè)結(jié)點(diǎn)都是連通的，則稱G是連通圖。現(xiàn)在是7頁(yè)\一共有38頁(yè)\編輯于星期日3。圖G中的極大連通子圖稱為圖G的支，圖G的支數(shù)記為(G)。圖G連通當(dāng)且僅當(dāng)(G)=1。

例：下圖中(G)=3。v1v6v4v7v5v2v3v8現(xiàn)在是8頁(yè)\一共有38頁(yè)\編輯于星期日4。連通圖G=(V,E)的點(diǎn)割集定義：設(shè)SV，如果(G-S)>1，則稱S是G的一個(gè)點(diǎn)割集。

①S是G的一個(gè)點(diǎn)割集，而S的任何真子集都不是點(diǎn)割集時(shí)，稱S是G的一個(gè)基本點(diǎn)割集。如S1={v2，v5}，S2={v2，v6},S3={v2，v7}，S4={v3，v5},S5={v4}②由單個(gè)結(jié)點(diǎn)（如u）構(gòu)成的點(diǎn)割集簡(jiǎn)稱為割點(diǎn)。v1v6v4v7v5v2v3現(xiàn)在是9頁(yè)\一共有38頁(yè)\編輯于星期日定理結(jié)點(diǎn)u是圖G的割點(diǎn)當(dāng)且僅當(dāng)存在兩結(jié)點(diǎn)v和w，使v到w的任何道路都經(jīng)過(guò)u。證明要點(diǎn)：“”,當(dāng)u是割點(diǎn)時(shí)，則Gu至少有2支，從這2支中各選一個(gè)結(jié)點(diǎn)即可?！啊?反之，如果v到w的任何道路都經(jīng)過(guò)u，則去掉u后，v和w各在Gu的1支中，即u是割點(diǎn)?，F(xiàn)在是10頁(yè)\一共有38頁(yè)\編輯于星期日5。連通圖G=(V,E)的邊割集定義：設(shè)FE，如果(G-F)>1，則稱F是G的一個(gè)邊割集。

①F是G的一個(gè)邊割集，而F的任何真子集都不是邊割集時(shí)，稱F是G的一個(gè)基本邊割集。如F1={v2v3，v3v7}，F(xiàn)2={v2v3，v5v7},F3={v1v4}，F(xiàn)4={v2v4，v2v6，v5v6},F5={v4v6，v2v6，v2v5，v3v7}②由單條邊（如uv）構(gòu)成的邊割集簡(jiǎn)稱為割邊。v1v6v4v5v2v3v7現(xiàn)在是11頁(yè)\一共有38頁(yè)\編輯于星期日定理邊e是圖G的割邊當(dāng)且僅當(dāng)e不在G的任何回路上。

證明要點(diǎn)：“”:當(dāng)e是割邊時(shí)，則Ge有2支，因而e不在G的任何回路上。“”:反之，如果e不在任何回路上，則去掉e后，e關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)各在Ge的1支中，即e是割邊。

現(xiàn)在是12頁(yè)\一共有38頁(yè)\編輯于星期日

6.圖的連通度(限無(wú)環(huán)圖G)(1)點(diǎn)連通度:記為К(G),定義為 最小基本點(diǎn)割集基數(shù), 當(dāng)GKn

К(G) n1, 當(dāng)GKn例如下圖中,К(G)2v1v6v4v5v2v3v7v8現(xiàn)在是13頁(yè)\一共有38頁(yè)\編輯于星期日(2)邊連通度:記為λ(G),定義為 最小基本邊割集基數(shù), 當(dāng)GK1

λ(G) 0, 當(dāng)GK1例如下圖中,К(G)2,

λ(G)2v1v6v4v5v2v3v7v8現(xiàn)在是14頁(yè)\一共有38頁(yè)\編輯于星期日練習(xí):求下列圖的К(G),

λ(G),和К(G)=2λ(G)=2=2К(G)=2λ(G)=2=2К(G)=2λ(G)=3=4現(xiàn)在是15頁(yè)\一共有38頁(yè)\編輯于星期日(3)連通度定理:К(G)λ(G)證明要點(diǎn):首先,每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊構(gòu)成一個(gè)邊割集,于是λ(G).下面證明К(G)λ(G)：首先注意對(duì)每個(gè)基本邊割集F，(G-F)=2；其次設(shè)F含λ(G)條邊，G-F的2支為G1和G2，若G不是二部圖，則去掉這支中與F關(guān)聯(lián)的全部結(jié)點(diǎn)即可；若G是二部圖，則交替刪去這2支中與F關(guān)聯(lián)的結(jié)點(diǎn)即可。現(xiàn)在是16頁(yè)\一共有38頁(yè)\編輯于星期日四、有向圖的道路1。定義：如果圖G中由結(jié)點(diǎn)和邊交替構(gòu)成的序列p=v0e1v1e2v2...ekvk,滿足其中每條ei是vi-1的出邊和vi的入邊，則稱p為由v0到vk的一條有向道路。在下圖中，一些有向道路p1=v1v4v2v1v3v5v4 p2=v3v2v1v3v5v4v2

p3=v5v4v2v1v3v1v2v3v4v5現(xiàn)在是17頁(yè)\一共有38頁(yè)\編輯于星期日2。有向道路的分類：①有向跡：任何滿足定義的有向道路。②有向簡(jiǎn)單道路：邊不重復(fù)的有向道路。③有向基本道路：結(jié)點(diǎn)不重復(fù)的有向道路。3。有向回路：起點(diǎn)和終點(diǎn)相同的有向道路。邊不重復(fù)的有向回路稱為有向簡(jiǎn)單回路。結(jié)點(diǎn)不重復(fù)的有向回路稱為有向圈，現(xiàn)在是18頁(yè)\一共有38頁(yè)\編輯于星期日在下圖中，一些有向回路p1=v1v4v2v1v3v5v4v2v1p2=v3v2v1v3v5v4v3p3=v5v4v2v1v3v5v1v2v3v4v5現(xiàn)在是19頁(yè)\一共有38頁(yè)\編輯于星期日五、有向圖的連通問(wèn)題1。如果存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的有向道路，則稱u可達(dá)v。結(jié)點(diǎn)集V上的“可達(dá)”關(guān)系具有性質(zhì)：自反、傳遞。定理：如果在n階有向圖中結(jié)點(diǎn)u可達(dá)v，則必存在從結(jié)點(diǎn)u到結(jié)點(diǎn)v的長(zhǎng)度不超過(guò)n-1的有向道路。現(xiàn)在是20頁(yè)\一共有38頁(yè)\編輯于星期日2。有向圖G的連通有如下三個(gè)層次：①?gòu)?qiáng)連通圖：任何一對(duì)不同結(jié)點(diǎn)都相互可達(dá)。②單向連通圖：任何一對(duì)不同結(jié)點(diǎn)間，至少?gòu)囊粋€(gè)結(jié)點(diǎn)可達(dá)另一個(gè)結(jié)點(diǎn)。③弱連通圖：不看邊的方向時(shí)是連通的。

abcd單向連通弱連通abcdabcd強(qiáng)連通現(xiàn)在是21頁(yè)\一共有38頁(yè)\編輯于星期日3。強(qiáng)連通的性質(zhì)①死鎖問(wèn)題的強(qiáng)連通背景②定理:有向圖G是強(qiáng)連通圖當(dāng)且僅當(dāng)存在一條包含所有結(jié)點(diǎn)的有向回路。證明要點(diǎn)：當(dāng)G強(qiáng)連通時(shí),據(jù)定義可依次構(gòu)造道路v1v2

v3…vn

v1,反過(guò)來(lái)是明顯的.③定義：有向圖G的極大強(qiáng)連通子圖稱為強(qiáng)分圖。例：下面有３個(gè)強(qiáng)分圖:G({v2,

v3,

v4}),G({v5,

v6})G({v1})v1v2v5v3v4v6現(xiàn)在是22頁(yè)\一共有38頁(yè)\編輯于星期日定理：每個(gè)結(jié)點(diǎn)都只位于一個(gè)強(qiáng)分圖中。證明要點(diǎn)：強(qiáng)連通是結(jié)點(diǎn)集合上的一個(gè)等價(jià)關(guān)系，由每個(gè)等價(jià)類誘導(dǎo)的子圖是一個(gè)強(qiáng)分圖．

現(xiàn)在是23頁(yè)\一共有38頁(yè)\編輯于星期日作業(yè)：習(xí)題9。21、2、5(吳子華)or習(xí)題10。31、2、5(馮偉森)附加題1：證明>1的圖必含回路，反之成立嗎？附加題2：證明連通圖的1度結(jié)點(diǎn)不是割點(diǎn)?，F(xiàn)在是24頁(yè)\一共有38頁(yè)\編輯于星期日第三節(jié)圖的矩陣表示一、鄰接矩陣1。設(shè)G=(V,E)是有向簡(jiǎn)單圖,其中V={v1,v2,...,vn},定義矩陣A=(aij)

nn如下:1如果(vi,vj)Eaij=0如果(vi,vj)E

稱A為G的鄰接矩陣.現(xiàn)在是25頁(yè)\一共有38頁(yè)\編輯于星期日下面有向圖對(duì)應(yīng)的鄰接矩陣是v1v2v3v4v5v100110v210110A=v300001v400100v500010v1v2v5v3v4現(xiàn)在是26頁(yè)\一共有38頁(yè)\編輯于星期日2。鄰接矩陣的性質(zhì)：①鄰接矩陣等價(jià)地描述了有向圖的信息。矩陣行和等于結(jié)點(diǎn)出度，列和等于入度。②設(shè)A2=(a(2)ij)，則

a(2)ij=1kn

(aikakj)

a(2)ij

0當(dāng)且僅當(dāng)至少存在aik=1且

akj=1，也就是存在從vi到vj的長(zhǎng)度為2的有向道路。因此

a(2)ij的值表達(dá)了從vi到vj的長(zhǎng)度為2的有向道路數(shù)目?，F(xiàn)在是27頁(yè)\一共有38頁(yè)\編輯于星期日例如，對(duì)于前面的鄰結(jié)矩陣v1v2v3v4v5v100101v200211A2=v300010v400001v500100

從中可以看出，存在一條從v1到v3的長(zhǎng)度為2的道路，2條從v2到v3的長(zhǎng)度為2的道路，1條從v4到v5的長(zhǎng)度為2的道路，不存在從v5到v2的長(zhǎng)度為2的道路等等。v1v2v5v3v4現(xiàn)在是28頁(yè)\一共有38頁(yè)\編輯于星期日v1v2v3v4v5

v100011v200112A3=v3

00100v400010v500001v1v2v5v3v4現(xiàn)在是29頁(yè)\一共有38頁(yè)\編輯于星期日類似地，可以構(gòu)造0011000121A4=000010010000010可對(duì)照?qǐng)D找出長(zhǎng)度為4的有向道路.③設(shè)Am=(a(m)ij)，那么a(m)ij的值表達(dá)了從vi到vj長(zhǎng)度為m的有向道路數(shù)目。a(m)ii的值表達(dá)了通過(guò)vi的長(zhǎng)度為m的有向回路數(shù)目。

現(xiàn)在是30頁(yè)\一共有38頁(yè)\編輯于星期日3。可達(dá)矩陣設(shè)G=(V,E)是有向簡(jiǎn)單圖,其中V={v1,v2,...,vn},定義矩陣P=(pij)

nn如下:1vi非平凡可達(dá)vjpij=0其它

稱P為G的可達(dá)矩陣.現(xiàn)在是31頁(yè)\一共有38頁(yè)\編輯于星期日可達(dá)矩陣P可通過(guò)鄰結(jié)矩陣A求得，方法之一是計(jì)算矩陣和：B=A+A2+...

+An-1然后，令pij=1當(dāng)且僅當(dāng)bij>0。例如，由前面的例子可得現(xiàn)在是32頁(yè)\一共有38頁(yè)\編輯于星期日B=A+A2+A3+A40033210554=001120021100121其中每個(gè)非0的bij表達(dá)了vi到vj的長(zhǎng)度不超過(guò)4的道路數(shù)目，若bij=0，表明不存在從vi到vj的非平凡道路。

v1v2v5v3v4現(xiàn)在是33頁(yè)\一共有38頁(yè)\編輯于星期日由矩陣B直接可導(dǎo)出下面的可達(dá)矩陣：0011110111P=001110011100111可達(dá)矩陣也可以利用Warshall算法求得。v1v2v5v3v4現(xiàn)在是34頁(yè)\一共有38頁(yè)\編輯于星期日4。由可達(dá)矩陣構(gòu)造圖的強(qiáng)分圖令Q=PPT=(qij)

nn，其中1i=jqij=pijpjiij那么，在矩陣Q中第k行中元素1對(duì)應(yīng)列的結(jié)點(diǎn)，構(gòu)成圖的一個(gè)強(qiáng)分圖?，F(xiàn)在是35頁(yè)\一共有38頁(yè)\編輯于星期日例：根據(jù)前面例子得到的可達(dá)矩陣，可得00111010001011100000PPT

=00111