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

1、計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)(上)第2編 圖 論,第三章 圖的基本概念,3.1 圖的概念與性質(zhì),一、圖的定義與表示 1。圖 由結(jié)點(diǎn)的集合V和邊的集合E組成的有序?qū)?稱為圖G。 2。有向圖、無(wú)向圖 每條邊都是有向邊的圖稱為有向圖，每條邊都是 無(wú)向邊的圖稱為無(wú)向圖，否則稱為混合圖。 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ù)，記

2、作deg(v)。其中以v為始點(diǎn)的邊 數(shù)稱為出度deg+(v)，以v為終點(diǎn)的邊數(shù)成為入度deg-(v) 因此有 圖G中結(jié)點(diǎn)的最大、最小度數(shù)記做(G)、(G,二、圖的基本概念與握手定理 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： 設(shè)圖G=，則下列結(jié)論成立的是 。 A) B) C) D) 例題3： 設(shè)簡(jiǎn)單連通無(wú)向圖G有12條邊，G中有2個(gè)1度結(jié)點(diǎn), 2個(gè)2度結(jié)點(diǎn)，3

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

4、向完全圖Kn的邊數(shù)為： 例題4： 設(shè)圖G是有n個(gè)結(jié)點(diǎn)的無(wú)向完全圖，則G的邊數(shù)為 。 A) n(n-1) B) n(n+1) C) D,C,5。正則圖 若無(wú)向簡(jiǎn)單圖G中每個(gè)結(jié)點(diǎn)的度數(shù)都為k，則G稱 為k-正則圖。 6。賦權(quán)圖 若圖G中的每一條邊都有一個(gè)表示長(zhǎng)度的實(shí)數(shù)， 則圖G稱為賦權(quán)圖或網(wǎng)絡(luò)。圖G為無(wú)向圖稱為無(wú)向賦權(quán) 圖，圖G為有向圖稱為有向賦權(quán)圖。 7。補(bǔ)圖 由圖G中的所有結(jié)點(diǎn)和構(gòu)成完全圖需添加的邊所組成的圖稱為G的補(bǔ)圖，記作,例題5： 已知圖的結(jié)點(diǎn)集 以及圖G和圖D的 邊集合分別為： 試作圖G和圖D，寫(xiě)出各結(jié)點(diǎn)的度數(shù)，回答圖G、圖D 是簡(jiǎn)單圖還是多重圖？ 解：a d a d b c b c

5、圖G 圖D,圖G： 圖D： 圖G不是簡(jiǎn)單無(wú)向圖，圖D是簡(jiǎn)單有向圖。 8、子圖 1。已知圖G=，如果 則G=稱為G的子圖。 2。如果 ，則稱G為G的真子圖。 3。如果 ，則稱G為G的生成子圖,三、圖的同構(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)的必要條件，但不是充分條 件，也就是說(shuō)，兩個(gè)圖即使?jié)M足上述條件也不一定同 構(gòu)。如果把其中一個(gè)圖中的結(jié)點(diǎn)重新排列，邊跟著結(jié) 點(diǎn)移動(dòng)，并且可以任意彎曲，能夠與另一圖完全 重合，那么

6、這兩個(gè)圖是同構(gòu)的,四、通路與回路 1。通路、回路 在G=中，如果從結(jié)點(diǎn)v0依次經(jīng)過(guò)邊和結(jié) 點(diǎn)可以到達(dá)vn，則稱v0與vn間存在通路，或v0與vn連 通，記作v0vn ，如v0vn則稱為回路。通路經(jīng)過(guò) 的邊數(shù)稱為通路的的長(zhǎng)度。 2。簡(jiǎn)單通路、簡(jiǎn)單回路 沒(méi)有重復(fù)邊的通路稱為簡(jiǎn)單通路，沒(méi)有重復(fù)邊 的回路稱為簡(jiǎn)單回路。 3?；就?、基本回路 沒(méi)有重復(fù)結(jié)點(diǎn)的通路稱為基本通路，沒(méi)有重復(fù) 結(jié)點(diǎn)的回路稱為基本回路,例題6： 設(shè)G如圖，已知通路 試回答它們各是簡(jiǎn)單通路、簡(jiǎn)單回路、基本通路 和基本回路。 解：是簡(jiǎn)單通路，基本通路，是簡(jiǎn)單回路，但不 是基本回路，是簡(jiǎn)單回路，基本回路，是簡(jiǎn)單通 路，但不是基本通路,

7、v1 v2 v5 v3 v4,一、連通性 若在無(wú)向圖G中，任何兩個(gè)不同的結(jié)點(diǎn)都是連通的 則稱G是連通圖。 無(wú)向圖中結(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)一定在同一連通分支中。 無(wú)向圖G的連通分支數(shù)記作W(G,3.2 圖的連通性,例如G： G不是連通圖，但可以劃分為三個(gè)連通分支。 是一個(gè)連通分支， 是一個(gè)連 通分支， 是一個(gè)連通分支。 稱為V的一個(gè)劃分,二、有向連通圖 1。強(qiáng)連通圖、單側(cè)連通圖、弱連通圖

8、在有向簡(jiǎn)單圖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è)連通圖 弱連通圖,2。兩個(gè)定理 定理6 一個(gè)有向圖是強(qiáng)連通的充分必要條件是存在一條至少經(jīng)過(guò)每個(gè)結(jié)點(diǎn)一次的回路。 定理7 在有向圖中，它的每個(gè)結(jié)點(diǎn)必位于且僅位于一個(gè)強(qiáng)分圖中。 例題7： 設(shè)Va,b,c,d,與V能構(gòu)成強(qiáng)連通圖的邊集E( ) (A) , (B) , (C) , (D),三、連通度 1。點(diǎn)割集 在無(wú)向連通圖G=中，若刪除結(jié)點(diǎn)集V(包括 所有與V中的

9、結(jié)點(diǎn)關(guān)聯(lián)的邊)，得到子圖GV。若V 是使GV不連通的最小點(diǎn)集，則稱V是G的一個(gè)點(diǎn) 割集。若V中只有一個(gè)結(jié)點(diǎn)則稱為割點(diǎn)。 換句話說(shuō)，點(diǎn)割集是指使圖G從連通圖變成不連 通圖需要?jiǎng)h除的最小點(diǎn)集。 例如，G： 刪除v1后G1,刪除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)樗皇亲钚↑c(diǎn)集。 例題8： 給定圖G，則圖G的點(diǎn)割集 是,2。邊割集 在無(wú)向連通圖G=中，若刪除邊集E，得到 子圖GE。若E是使GE不連通的最小邊集，則稱 E是G的一個(gè)邊割集。若E中僅一條邊則稱為割邊。 換句話說(shuō)，邊割集是指使圖G的從連通

10、圖變成不 連通圖需要?jiǎng)h除的最小邊集。 例如，G： 刪除邊(v1,v2)后G1,刪除(v1,v2),(v2,v3)后G2 刪除(v3,v5)后G3 因此，(v1,v2)不是邊割集，W(G1)=1， (v1,v2),(v2,v3)是邊割集，W(G2)=2， (v3,v5)是邊割集，也是割邊， W(G3)=2,3。連通度 (一)點(diǎn)連通度 若G是無(wú)向連通圖，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

11、是非連通圖，則,二)邊連通度 若G是無(wú)向連通圖，E是G的邊數(shù)最少的邊割集， 則E中的邊數(shù)稱為G的邊連通度，記作 。 因此， (1) 若G是平凡圖，則E=， ， (2) 若G存在割邊，則 ， (3) 若G是非連通圖，則 。 (三) 之間的關(guān)系 在無(wú)向圖G中，一定有： 即點(diǎn)連通度不大于邊連通度，邊連通度不大于結(jié) 點(diǎn)的最小度數(shù),3.3 圖的矩陣表示,一、無(wú)向圖的鄰接矩陣 對(duì)于無(wú)向圖G=，若|V|=n，作n階方陣A(G) 其中的 表示 相關(guān)聯(lián)的邊數(shù)。 例如圖G如下， 可以看出，A(G)是對(duì)稱矩陣。 主對(duì)角線上的元素表示各結(jié)點(diǎn)的自回路數(shù),二、有向圖的鄰接矩陣 對(duì)于有向圖D=，若|V|=n，作n階方陣A(

12、D) 其中的 表示從 的邊數(shù)。 從下例中可以看出A(D)不再是對(duì)稱矩陣。 矩陣中所有元素之和等于有向圖中的邊數(shù)。 第 行元素之和表示結(jié)點(diǎn) 的出度， 第 列元素之和表示結(jié)點(diǎn) 的入度， 圖D,例題9： 設(shè)有向圖D的鄰接矩陣為 A(D)= ， 那么E 。 例題10： 有向圖的鄰接矩陣(D)= 中第 行元素的 和 是中的結(jié)點(diǎn) 的,三、計(jì)算邊數(shù) 在鄰接矩陣A(D)中， 為長(zhǎng)度為1的邊數(shù)。 在A2(D)中， 為長(zhǎng)度為2的邊數(shù)。 一般地說(shuō)，在 中， 為長(zhǎng)度為 的邊 數(shù)。 位置 上的數(shù)表示從 長(zhǎng)度為 的邊數(shù)。 在A(D)+A2(D)+ +Ak(D)中， 為長(zhǎng)度小于等 于k的邊數(shù)之和，位置 上的數(shù)表示從 長(zhǎng)度小 于等于k的邊數(shù)之和,例如，在