1、計算機數學基礎(上)第2編 圖 論第三章第三章 圖的基本概念圖的基本概念3.1 圖的概念與性質 一、圖的定義與表示1。圖 由結點的集合v和邊的集合e組成的有序對稱為圖g。2。有向圖、無向圖 每條邊都是有向邊的圖稱為有向圖，每條邊都是無向邊的圖稱為無向圖，否則稱為混合圖。3。孤立點、零圖 不與其它結點相關聯的結點稱為孤立點，全部由孤立點構成的圖叫做零圖。4。邊的重數 具有相同始點和終點的邊稱為平行邊，平行邊的條數稱為邊的重數。5。n 階圖 具有n個結點的圖稱為n階圖，具有n個結點和m條邊的圖稱為(n,m)圖6。結點的度數 圖中與某結點v相關聯的邊數(自回路算兩條邊)，稱為該結點的度數，記作deg

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

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

4、邊相連，則g稱為二部圖。9x4。完全圖 每一對結點之間都有邊相連的無向簡單圖稱為無向完全圖，每一對結點之間都有方向相反的兩條邊相連的有向簡單圖稱為有向完全圖。 具有n個結點的無向完全圖kn的邊數為：例題4： 設圖g是有n個結點的無向完全圖，則g的邊數為 。 a) n(n-1) b) n(n+1) c) d) 1(21nn) 1(21nc2) 1(|nne5。正則圖 若無向簡單圖g中每個結點的度數都為k，則g稱為k-正則圖。6。賦權圖 若圖g中的每一條邊都有一個表示長度的實數，則圖g稱為賦權圖或網絡。圖g為無向圖稱為無向賦權圖，圖g為有向圖稱為有向賦權圖。7。補圖 由圖g中的所有結點和構成完全圖

5、需添加的邊所組成的圖稱為g的補圖，記作 。g例題5： 已知圖的結點集 以及圖g和圖d的邊集合分別為：試作圖g和圖d，寫出各結點的度數，回答圖g、圖d是簡單圖還是多重圖？ 解：a d a d b c b c 圖g 圖d,dcbav ),(),(),(),()(cacbbaaage,)(bcacdccabade圖g：圖d：圖g不是簡單無向圖，圖d是簡單有向圖。 8、子圖 1。已知圖g=，如果則g=稱為g的子圖。 2。如果 ，則稱g為g的真子圖。 3。如果 ，則稱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中的結點集v與圖g中的結點集v具有一一對應的關系，并且對應的邊都具有相同的重數，則稱g與g同構，記作 。 因此，兩圖同構必須滿足下列條件： 結點數相同， 邊數相同， 度數相同的結點數相同。 上述條件是兩圖同構的必要條件，但不是充分條件，也就是說，兩個圖即使滿足上述條件也不一定同構。如果把其中一個圖中的結點重新排列，邊跟著結點移動，并且可以任意彎曲，能夠與另一圖完全重合，那么這兩個圖是同構的。gg 四、通路與回路1。通路、回路 在g=中，如果從結點v0依次經過邊

7、和結點可以到達vn，則稱v0與vn間存在通路，或v0與vn連通，記作v0vn ，如v0vn則稱為回路。通路經過的邊數稱為通路的的長度。2。簡單通路、簡單回路 沒有重復邊的通路稱為簡單通路，沒有重復邊的回路稱為簡單回路。3。基本通路、基本回路 沒有重復結點的通路稱為基本通路，沒有重復結點的回路稱為基本回路。例題6： 設g如圖，已知通路 試回答它們各是簡單通路、簡單回路、基本通路和基本回路。解：是簡單通路，基本通路，是簡單回路，但不是基本回路，是簡單回路，基本回路，是簡單通路，但不是基本通路。 v1 v2 v5 v3 v41e2e3e4e5e6e7e8e3227551vevevev57284332

8、265vevevevevev26572vevev56284332211vevevevevev一、連通性 若在無向圖g中，任何兩個不同的結點都是連通的則稱g是連通圖。 無向圖中結點的連通關系具有自反性、對稱性和傳遞性，所以結點的連通關系是等價關系。 若圖g不是連通圖，但如果把g分成幾個部分，每一個部分都是連通的，則每一個部分稱為一個連通子圖，每一個連通子圖g稱為g的一個連通分支。 g中相互連通的結點一定在同一連通分支中。 無向圖g的連通分支數記作w(g)。 3.2 圖的連通性 例如g： g不是連通圖，但可以劃分為三個連通分支。 是一個連通分支， 是一個連通分支， 是一個連通分支。 稱為v的一個劃

9、分。1v,7654321vvvvvvv2v3v5v4v6v7v),(5432vvvvg)(1vg),(76vvg3)(gw二、有向連通圖 1。強連通圖、單側連通圖、弱連通圖在有向簡單圖d中， (1) 若任何兩個結點間都可以到達則稱為強連通圖 (2) 若任何兩個結點間，總有一個結點可以到達另一個結點，則稱為單側連通圖， (3) 若在不考慮邊的方向的情況下圖是連通的，則稱為弱連通圖。連通圖舉例 強連通圖 單側連通圖 弱連通圖abcdddbbccaa2。兩個定理定理6 一個有向圖是強連通的充分必要條件是存在一條至少經過每個結點一次的回路。定理7 在有向圖中，它的每個結點必位于且僅位于一個強分圖中。例

10、題7： 設va,b,c,d,與v能構成強連通圖的邊集e( )(a) , (b) , (c) , (d) ,a三、連通度1。點割集 在無向連通圖g=中，若刪除結點集v(包括所有與v中的結點關聯的邊)，得到子圖gv。若v是使gv不連通的最小點集，則稱v是g的一個點割集。若v中只有一個結點則稱為割點。 換句話說，點割集是指使圖g從連通圖變成不連通圖需要刪除的最小點集。例如，g： 刪除v1后g1 1v1)(gw2v3v4v5v2v4v5v3v1)(1gw1v刪除v3后g2 刪除v1,v3后g3因此，v1不是點割集，w(g1)=1， v3是點割集，又是割點，w(g2)=2 v1,v3不是點割集，因為它不

11、是最小點集。例題8： 給定圖g，則圖g的點割集是 。,ecf 和2v4v5v2)(2gw1v2v5v4v3)(3gw3v3v1vabcdef 2。邊割集 在無向連通圖g=中，若刪除邊集e，得到子圖ge。若e是使ge不連通的最小邊集，則稱e是g的一個邊割集。若e中僅一條邊則稱為割邊。 換句話說，邊割集是指使圖g的從連通圖變成不連通圖需要刪除的最小邊集。 例如，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。連通度(一)點連通度 若g是無向連通圖，v是g的結點數最少的點割集或gv是平凡圖(孤點)，則v中的結點數稱為g的點連通度，記作 。 因此， (1) 若g是平凡圖，則v=， ， (2) 若g是完全圖，去掉n-1個結點才能成為平凡圖，所以 ， (3) 若g存在割點，則 ， (4) 若g是非連通圖，則 。)(g0)(g1)( nkn1)(g0)(g(二)邊連通度 若g是無向連通圖，e是g的邊數最少的邊割集，則e中的邊數稱為g的邊連通度，記作 。 因此，

13、 (1) 若g是平凡圖，則e=， ， (2) 若g存在割邊，則 ， (3) 若g是非連通圖，則 。(三) 之間的關系 在無向圖g中，一定有： 即點連通度不大于邊連通度，邊連通度不大于結點的最小度數。 )(g0)(g)()()(ggg1)(g)()(),(ggg和0)(g3.3 圖的矩陣表示一、無向圖的鄰接矩陣 對于無向圖g=，若|v|=n，作n階方陣a(g)其中的 表示 相關聯的邊數。 例如圖g如下， 可以看出，a(g)是對稱矩陣。 主對角線上的元素表示各結點的自回路數。1v2v3v1e3e2e4vijajivv與0000001001010011)(ga二、有向圖的鄰接矩陣 對于有向圖d=，若

14、|v|=n，作n階方陣a(d)其中的 表示從 的邊數。 從下例中可以看出a(d)不再是對稱矩陣。 矩陣中所有元素之和等于有向圖中的邊數。 第 行元素之和表示結點 的出度， 第 列元素之和表示結點 的入度，圖d：1v2v3v1e3e2e4e001100110)(daijajivv指向iivjvj例題9： 設有向圖d的鄰接矩陣為 a(d)= ，那么e 。 例題10： 有向圖的鄰接矩陣(d)= 中第 行元素的和 是中的結點 的 。 71100100001000120nija injija1iv出度三、計算邊數 在鄰接矩陣a(d)中， 為長度為1的邊數。 在a2(d)中， 為長度為2的邊數。 一般地說

15、，在 中， 為長度為 的邊數。 位置 上的數表示從 長度為 的邊數。 在a(d)+a2(d)+ +ak(d)中， 為長度小于等于k的邊數之和，位置 上的數表示從 長度小于等于k的邊數之和。)(dal)(daaijijaija)()2(2daaijija)()(daallijijalljivv 到ijaijajivv 到例如，在前例中 長度為2的邊共有5條，從 的回路有1條。 長度小于等于2的邊共有9條。5,110001101001100110001100110)(2ijada33vv 到9,111101211110001101001100110)()(2ijadada例題11： 設有向圖d=，求d中v2到v4長度分別為1，2，3 的通路的條數。解：100101011003000101001001010200010100100101020001)(,0100100101020001)(2dada010110020103000101001001010200011001010110030001)(3da1v2v3v4v 的通路和沒有長度為條的通路有長度為3112，例題12： 已知圖d的鄰接矩陣為求從v2到v4長度為2和從v3到v3長度為2的通路條數，并將它們具體寫出.解： 1v2v3v4v0101101001011110)(da212002022120121201