離散數(shù)學(xué)第3章圖的基本概念ppt課件

1、計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)第2編 圖 論第三章第三章 圖的基本概念圖的基本概念3.1 圖的概念與性質(zhì) 一、圖的定義與表示1。圖 由結(jié)點(diǎn)的集合V和邊的集合E組成的有序?qū)ΨQ為圖G。2。有向圖、無向圖 每條邊都是有向邊的圖稱為有向圖，每條邊都是無向邊的圖稱為無向圖，否則稱為混合圖。3。孤立點(diǎn)、零圖 不與其它結(jié)點(diǎn)相關(guān)聯(lián)的結(jié)點(diǎn)稱為孤立點(diǎn)，全部由孤立點(diǎn)構(gòu)成的圖叫做零圖。4。邊的重?cái)?shù) 具有相同始點(diǎn)和終點(diǎn)的邊稱為平行邊，平行邊的條數(shù)稱為邊的重?cái)?shù)。5。n 階圖 具有n個(gè)結(jié)點(diǎn)的圖稱為n階圖，具有n個(gè)結(jié)點(diǎn)和m條邊的圖稱為(n,m)圖6。結(jié)點(diǎn)的度數(shù) 圖中與某結(jié)點(diǎn)v相關(guān)聯(lián)的邊數(shù)(自回路算兩條邊)，稱為該結(jié)點(diǎn)的度數(shù)，記作deg

2、(v)。其中以v為始點(diǎn)的邊數(shù)稱為出度deg+(v)，以v為終點(diǎn)的邊數(shù)成為入度deg-(v) 因此有 圖G中結(jié)點(diǎn)的最大、最小度數(shù)記做(G)、(G)(deg)(deg)deg(vvv二、圖的基本概念與握手定理1。握手定理 圖G中所有結(jié)點(diǎn)的度數(shù)之和等于邊數(shù)的二倍。推論1 在任何圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)數(shù)必為偶數(shù)。 推論2 在有向圖中，所有結(jié)點(diǎn)的入度之和等于所有結(jié)點(diǎn)的出度之和。例題1： 已知圖G中有1個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)3度結(jié)點(diǎn)，4個(gè)4度結(jié)點(diǎn)，則G的邊數(shù)是 。解： |2)(EvgdeVv15|,|23044332211)(degEEv例題2： 設(shè)圖G=，則下列結(jié)論成立的是 。 A) B) C)

3、 D)例題3： 設(shè)簡單連通無向圖G有12條邊，G中有2個(gè)1度結(jié)點(diǎn),2個(gè)2度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)為3，求G中有多少個(gè)結(jié)點(diǎn)。試作一個(gè)滿足該條件的簡單無向圖。解:設(shè)G中有x個(gè)結(jié)點(diǎn)，則3度的結(jié)點(diǎn)有x-7。根據(jù)握手定理有，|2)deg(EV |)deg(EV |2)(EvegdVv|)(EvegdVvC122)7(3342221x解得 ,故G中有9個(gè)結(jié)點(diǎn)。滿足條件的圖如下：2。簡單圖 不含平行邊和環(huán)(自回路)的圖稱為簡單圖。 在簡單圖中，任何結(jié)點(diǎn)的度數(shù)都小于等于n-1。這是判斷一個(gè)度數(shù)序列能否構(gòu)成簡單圖的主要依據(jù)。3。二部圖 若將無向圖G的結(jié)點(diǎn)集分為兩部分，而每一部分中任何兩個(gè)結(jié)點(diǎn)之間都沒有

4、邊相連，則G稱為二部圖。9x4。完全圖 每一對(duì)結(jié)點(diǎn)之間都有邊相連的無向簡單圖稱為無向完全圖，每一對(duì)結(jié)點(diǎn)之間都有方向相反的兩條邊相連的有向簡單圖稱為有向完全圖。 具有n個(gè)結(jié)點(diǎn)的無向完全圖Kn的邊數(shù)為：例題4： 設(shè)圖G是有n個(gè)結(jié)點(diǎn)的無向完全圖，則G的邊數(shù)為 。 A) n(n-1) B) n(n+1) C) D) 1(21nn) 1(21nC2) 1(|nnE5。正則圖 若無向簡單圖G中每個(gè)結(jié)點(diǎn)的度數(shù)都為k，則G稱為k-正則圖。6。賦權(quán)圖 若圖G中的每一條邊都有一個(gè)表示長度的實(shí)數(shù)，則圖G稱為賦權(quán)圖或網(wǎng)絡(luò)。圖G為無向圖稱為無向賦權(quán)圖，圖G為有向圖稱為有向賦權(quán)圖。7。補(bǔ)圖 由圖G中的所有結(jié)點(diǎn)和構(gòu)成完全圖

5、需添加的邊所組成的圖稱為G的補(bǔ)圖，記作 。G例題5： 已知圖的結(jié)點(diǎn)集 以及圖G和圖D的邊集合分別為：試作圖G和圖D，寫出各結(jié)點(diǎn)的度數(shù)，回答圖G、圖D是簡單圖還是多重圖？ 解：a d a d b c b c 圖G 圖D,dcbaV ),(),(),(),()(cacbbaaaGE,)(bcacdccabaDE圖G：圖D：圖G不是簡單無向圖，圖D是簡單有向圖。 8、子圖 1。已知圖G=，假設(shè)則G=稱為G的子圖。 2。假設(shè) ，則稱G為G的真子圖。 3。假設(shè) ，則稱G為G的生成子圖。EEVV,EEVV,EEVV或0)deg(, 2)deg(, 2)deg(, 4)deg(dcba2)(deg, 0)(

6、deg, 1)(deg, 2)(degbbaa1)(deg, 0)(deg, 1)(deg, 3)(degddcc三、圖的同構(gòu) 如果圖G中的結(jié)點(diǎn)集V與圖G中的結(jié)點(diǎn)集V具有一一對(duì)應(yīng)的關(guān)系，并且對(duì)應(yīng)的邊都具有相同的重?cái)?shù)，則稱G與G同構(gòu)，記作 。 因此，兩圖同構(gòu)必須滿足下列條件： 結(jié)點(diǎn)數(shù)相同， 邊數(shù)相同， 度數(shù)相同的結(jié)點(diǎn)數(shù)相同。 上述條件是兩圖同構(gòu)的必要條件，但不是充分條件，也就是說，兩個(gè)圖即使?jié)M足上述條件也不一定同構(gòu)。如果把其中一個(gè)圖中的結(jié)點(diǎn)重新排列，邊跟著結(jié)點(diǎn)移動(dòng)，并且可以任意彎曲，能夠與另一圖完全重合，那么這兩個(gè)圖是同構(gòu)的。GG 四、通路與回路1。通路、回路 在G=中，如果從結(jié)點(diǎn)v0依次經(jīng)過邊

7、和結(jié)點(diǎn)可以到達(dá)vn，則稱v0與vn間存在通路，或v0與vn連通，記作v0vn ，如v0vn則稱為回路。通路經(jīng)過的邊數(shù)稱為通路的的長度。2。簡單通路、簡單回路 沒有重復(fù)邊的通路稱為簡單通路，沒有重復(fù)邊的回路稱為簡單回路。3。基本通路、基本回路 沒有重復(fù)結(jié)點(diǎn)的通路稱為基本通路，沒有重復(fù)結(jié)點(diǎn)的回路稱為基本回路。例題6： 設(shè)G如圖，已知通路 試回答它們各是簡單通路、簡單回路、基本通路和基本回路。解：是簡單通路，基本通路，是簡單回路，但不是基本回路，是簡單回路，基本回路，是簡單通路，但不是基本通路。 v1 v2 v5 v3 v41e2e3e4e5e6e7e8e3227551vevevev57284332

8、265vevevevevev26572vevev56284332211vevevevevev一、連通性 若在無向圖G中，任何兩個(gè)不同的結(jié)點(diǎn)都是連通的則稱G是連通圖。 無向圖中結(jié)點(diǎn)的連通關(guān)系具有自反性、對(duì)稱性和傳遞性，所以結(jié)點(diǎn)的連通關(guān)系是等價(jià)關(guān)系。 若圖G不是連通圖，但如果把G分成幾個(gè)部分，每一個(gè)部分都是連通的，則每一個(gè)部分稱為一個(gè)連通子圖，每一個(gè)連通子圖G稱為G的一個(gè)連通分支。 G中相互連通的結(jié)點(diǎn)一定在同一連通分支中。 無向圖G的連通分支數(shù)記作W(G)。 3.2 圖的連通性 例如G： G不是連通圖，但可以劃分為三個(gè)連通分支。 是一個(gè)連通分支， 是一個(gè)連通分支， 是一個(gè)連通分支。 稱為V的一個(gè)劃

9、分。1v,7654321vvvvvvv2v3v5v4v6v7v),(5432vvvvG)(1vG),(76vvG3)(GW二、有向連通圖 1。強(qiáng)連通圖、單側(cè)連通圖、弱連通圖在有向簡單圖D中， (1) 若任何兩個(gè)結(jié)點(diǎn)間都可以到達(dá)則稱為強(qiáng)連通圖 (2) 若任何兩個(gè)結(jié)點(diǎn)間，總有一個(gè)結(jié)點(diǎn)可以到達(dá)另一個(gè)結(jié)點(diǎn)，則稱為單側(cè)連通圖， (3) 若在不考慮邊的方向的情況下圖是連通的，則稱為弱連通圖。連通圖舉例 強(qiáng)連通圖 單側(cè)連通圖 弱連通圖abcdddbbccaa2。兩個(gè)定理定理6 一個(gè)有向圖是強(qiáng)連通的充分必要條件是存在一條至少經(jīng)過每個(gè)結(jié)點(diǎn)一次的回路。定理7 在有向圖中，它的每個(gè)結(jié)點(diǎn)必位于且僅位于一個(gè)強(qiáng)分圖中。例

10、題7： 設(shè)Va,b,c,d,與V能構(gòu)成強(qiáng)連通圖的邊集E( )(A) , (B) , (C) , (D) ,A三、連通度1。點(diǎn)割集 在無向連通圖G=中，若刪除結(jié)點(diǎn)集V(包括所有與V中的結(jié)點(diǎn)關(guān)聯(lián)的邊)，得到子圖GV。若V是使GV不連通的最小點(diǎn)集，則稱V是G的一個(gè)點(diǎn)割集。若V中只有一個(gè)結(jié)點(diǎn)則稱為割點(diǎn)。 換句話說，點(diǎn)割集是指使圖G從連通圖變成不連通圖需要?jiǎng)h除的最小點(diǎn)集。例如，G： 刪除v1后G1 1v1)(GW2v3v4v5v2v4v5v3v1)(1GW1v刪除v3后G2 刪除v1,v3后G3因此，v1不是點(diǎn)割集，W(G1)=1， v3是點(diǎn)割集，又是割點(diǎn)，W(G2)=2 v1,v3不是點(diǎn)割集，因?yàn)樗?/p>

11、是最小點(diǎn)集。例題8： 給定圖G，則圖G的點(diǎn)割集是 。,ecf 和2v4v5v2)(2GW1v2v5v4v3)(3GW3v3v1vabcdef 2。邊割集 在無向連通圖G=中，若刪除邊集E，得到子圖GE。若E是使GE不連通的最小邊集，則稱E是G的一個(gè)邊割集。若E中僅一條邊則稱為割邊。 換句話說，邊割集是指使圖G的從連通圖變成不連通圖需要?jiǎng)h除的最小邊集。 例如，G： 刪除邊(v1,v2)后G1 1v2v1)(GW4v2v3v4v5v5v3v1)(1GW1v刪除(v1,v2),(v2,v3)后G2 刪除(v3,v5)后G3因此，(v1,v2)不是邊割集，W(G1)=1， (v1,v2),(v2,v3

12、)是邊割集，W(G2)=2， (v3,v5)是邊割集，也是割邊， W(G3)=2。1v2v5v4v2)(2GW2)(3GW3v2v4v5v1v3v3。連通度(一)點(diǎn)連通度 若G是無向連通圖，V是G的結(jié)點(diǎn)數(shù)最少的點(diǎn)割集或GV是平凡圖(孤點(diǎn))，則V中的結(jié)點(diǎn)數(shù)稱為G的點(diǎn)連通度，記作 。 因此， (1) 若G是平凡圖，則V=， ， (2) 若G是完全圖，去掉n-1個(gè)結(jié)點(diǎn)才能成為平凡圖，所以 ， (3) 若G存在割點(diǎn)，那么 ， (4) 若G是非連通圖，那么 。)(G0)(G1)( nKn1)(G0)(G(二)邊連通度 若G是無向連通圖，E是G的邊數(shù)最少的邊割集，則E中的邊數(shù)稱為G的邊連通度，記作 。 因

13、此， (1) 若G是平凡圖，則E=， ， (2) 若G存在割邊，那么 ， (3) 若G是非連通圖，那么 。(三) 之間的關(guān)系 在無向圖G中，一定有： 即點(diǎn)連通度不大于邊連通度，邊連通度不大于結(jié)點(diǎn)的最小度數(shù)。 )(G0)(G)()()(GGG1)(G)()(),(GGG和0)(G3.3 圖的矩陣表示一、無向圖的鄰接矩陣 對(duì)于無向圖G=，假設(shè)|V|=n，作n階方陣A(G)其中的 表示 相關(guān)聯(lián)的邊數(shù)。 例如圖G如下， 可以看出，A(G)是對(duì)稱矩陣。 主對(duì)角線上的元素表示各結(jié)點(diǎn)的自回路數(shù)。1v2v3v1e3e2e4vijajivv與0000001001010011)(GA二、有向圖的鄰接矩陣 對(duì)于有向

14、圖D=，假設(shè)|V|=n，作n階方陣A(D)其中的 表示從 的邊數(shù)。 從下例中可以看出A(D)不再是對(duì)稱矩陣。 矩陣中所有元素之和等于有向圖中的邊數(shù)。 第 行元素之和表示結(jié)點(diǎn) 的出度， 第 列元素之和表示結(jié)點(diǎn) 的入度，圖D：1v2v3v1e3e2e4e001100110)(DAijajivv指向iivjvj例題9： 設(shè)有向圖D的鄰接矩陣為 A(D)= ，那么E 。 例題10： 有向圖的鄰接矩陣(D)= 中第 行元素的和 是中的結(jié)點(diǎn) 的 。 71100100001000120nija injija1iv出度三、計(jì)算邊數(shù) 在鄰接矩陣A(D)中， 為長度為1的邊數(shù)。 在A2(D)中， 為長度為2的邊數(shù)

15、。 一般地說，在 中， 為長度為 的邊數(shù)。 位置 上的數(shù)表示從 長度為 的邊數(shù)。 在A(D)+A2(D)+ +Ak(D)中， 為長度小于等于k的邊數(shù)之和，位置 上的數(shù)表示從 長度小于等于k的邊數(shù)之和。)(DAl)(DAaijijaija)()2(2DAaijija)()(DAallijijalljivv 到ijaijajivv 到例如，在前例中 長度為2的邊共有5條，從 的回路有1條。 長度小于等于2的邊共有9條。5,110001101001100110001100110)(2ijaDA33vv 到9,111101211110001101001100110)()(2ijaDADA例題11： 設(shè)有向圖D=，求D中v2到v4長度分別為1，2，3 的通路的條數(shù)。解：100101011003000101001001010200010100100101020001)(,0100100101020001)(2DADA010110020103000101001001010200011001010110030001)(3DA1v2v3v4v 的通路和沒有長度為條的通路有長度為3112，例題12： 已知圖D的鄰接矩陣為求從v2到v4長度為2和從v3到v3長度為2的通路條數(shù)，并將它們具體寫出.解： 1v2v3v4v0101101001011110)(DA212002022120121201