1、1離散數(shù)學(xué)CH7圖的基本概念1無向無向圖及有向圖圖及有向圖2 圖論的起源圖論的起源圖論是組合數(shù)學(xué)的圖論是組合數(shù)學(xué)的一個(gè)分支一個(gè)分支, ,它起源它起源于于17361736年歐拉的第年歐拉的第一篇關(guān)于圖論的論一篇關(guān)于圖論的論文，這篇論文解決文，這篇論文解決了著名的了著名的 “哥尼哥尼斯堡七橋問題斯堡七橋問題” ，從而使歐拉成為，從而使歐拉成為圖論的創(chuàng)始人。圖論的創(chuàng)始人。31.哥尼斯堡七橋問題 哥尼斯堡哥尼斯堡位于前蘇聯(lián)的加里位于前蘇聯(lián)的加里寧格勒，歷史上曾經(jīng)是德國寧格勒，歷史上曾經(jīng)是德國東普魯士省的省會(huì)，普雷格東普魯士省的省會(huì)，普雷格爾河橫穿城堡，河中有爾河橫穿城堡，河中有兩個(gè)兩個(gè)小島小島，共有，

2、共有七座橋七座橋連接兩岸連接兩岸和小島。和小島。 問題：問題： 在所有橋都只能走一在所有橋都只能走一遍的前提下，如何才能把這遍的前提下，如何才能把這個(gè)地方所有的橋都走遍？個(gè)地方所有的橋都走遍？4哥尼斯堡七橋問題尼斯堡七橋問題解決方式解決方式萊昂哈德萊昂哈德歐拉歐拉（Leonhard EulerLeonhard Euler）在）在17351735年圓滿地年圓滿地解決了這一問題，證明這種方法并不存在，也順帶解解決了這一問題，證明這種方法并不存在，也順帶解決了決了一筆畫問題一筆畫問題。他在圣彼得堡科學(xué)院發(fā)表了圖論史。他在圣彼得堡科學(xué)院發(fā)表了圖論史上第一篇重要文獻(xiàn)。歐拉把實(shí)際的抽象問題簡化為平上第一篇

3、重要文獻(xiàn)。歐拉把實(shí)際的抽象問題簡化為平面上的點(diǎn)與線組合，每一座橋視為一條線，橋所連接面上的點(diǎn)與線組合，每一座橋視為一條線，橋所連接的地區(qū)視為點(diǎn)。這樣若從某點(diǎn)出發(fā)后最后再回到這點(diǎn)的地區(qū)視為點(diǎn)。這樣若從某點(diǎn)出發(fā)后最后再回到這點(diǎn)，則這一點(diǎn)的線數(shù)必須是偶數(shù)。，則這一點(diǎn)的線數(shù)必須是偶數(shù)。 /wiki/File:Konigsberg_bridges.png 5圖論的起源歐拉最后給出任意一種河歐拉最后給出任意一種河橋圖能否全橋圖能否全部走一次的部走一次的判定法則判定法則。如果通。如果通奇數(shù)座奇數(shù)座橋的橋的地方地方不止兩個(gè)不止兩個(gè)，那么滿足要求的路線便不，那么滿足要求的路線便不

4、存在了。如果只有存在了。如果只有兩個(gè)地方兩個(gè)地方通奇數(shù)座橋，通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路則可從其中任何一地出發(fā)找到所要求的路線。若線。若沒有一個(gè)地方?jīng)]有一個(gè)地方通奇數(shù)座橋，則從任通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn)，他還何一地出發(fā)，所求的路線都能實(shí)現(xiàn)，他還說明了怎樣快速找到所要求的路線。說明了怎樣快速找到所要求的路線。不少數(shù)學(xué)家都嘗試去解析這個(gè)事例。而這不少數(shù)學(xué)家都嘗試去解析這個(gè)事例。而這些解析，最后發(fā)展成為了數(shù)學(xué)中的些解析，最后發(fā)展成為了數(shù)學(xué)中的圖論圖論。6 歐 拉 圖定義定義 一個(gè)圖一個(gè)圖, ,如果能夠從一點(diǎn)出如果能夠從一點(diǎn)出發(fā)發(fā), ,經(jīng)過每條邊一次且僅一次

5、再經(jīng)過每條邊一次且僅一次再回到起點(diǎn)回到起點(diǎn), ,則稱為則稱為歐拉圖歐拉圖 歐拉在論文中給出并證明了判歐拉在論文中給出并證明了判斷歐拉圖的充分必要條件定理斷歐拉圖的充分必要條件定理, ,并證并證明了七橋圖不是歐拉圖。明了七橋圖不是歐拉圖。7 從這個(gè)問題可以看出：圖圖：圖用點(diǎn)代表各個(gè)事物圖用點(diǎn)代表各個(gè)事物, ,用邊代用邊代表各個(gè)事物間的二元關(guān)系。表各個(gè)事物間的二元關(guān)系。 所以，圖是研究集合上的二元所以，圖是研究集合上的二元關(guān)系的工具，是建立數(shù)學(xué)模型的一關(guān)系的工具，是建立數(shù)學(xué)模型的一個(gè)重要手段。個(gè)重要手段。8 2、一百多年以后 “七橋七橋”問題以后，圖論的研究停滯了一問題以后，圖論的研究停滯了一百多

6、年，直到百多年，直到18471847年，基爾霍夫用年，基爾霍夫用“樹樹”圖解決了電路理論中的求解聯(lián)立方程圖解決了電路理論中的求解聯(lián)立方程的問題，十年后凱萊用的問題，十年后凱萊用 “樹樹” 圖計(jì)算有圖計(jì)算有機(jī)化學(xué)中的問題。在這一時(shí)期流行著兩機(jī)化學(xué)中的問題。在這一時(shí)期流行著兩個(gè)著名的圖論問題：哈密爾頓回路問題個(gè)著名的圖論問題：哈密爾頓回路問題和和 “四色猜想四色猜想” 問題。問題。93.哈密爾頓回路問題 18561856年年, ,英國數(shù)學(xué)家哈密爾頓設(shè)計(jì)英國數(shù)學(xué)家哈密爾頓設(shè)計(jì)了一個(gè)周游世界的游戲，他在一個(gè)了一個(gè)周游世界的游戲，他在一個(gè)正十二面體的二十個(gè)頂點(diǎn)上標(biāo)上二正十二面體的二十個(gè)頂點(diǎn)上標(biāo)上二十個(gè)著

7、名城市的名字，要求游戲者十個(gè)著名城市的名字，要求游戲者從一個(gè)城市出發(fā)，經(jīng)過每一個(gè)城市從一個(gè)城市出發(fā)，經(jīng)過每一個(gè)城市一次且僅一次，然后回到出發(fā)點(diǎn)。一次且僅一次，然后回到出發(fā)點(diǎn)。10哈密爾頓回路圖 此路線稱為：此路線稱為：哈密爾頓回路哈密爾頓回路， 而此圖稱為：而此圖稱為：哈密爾頓圖哈密爾頓圖。114、“四 色 猜 想” 問 題 人們?cè)陂L期為地圖人們?cè)陂L期為地圖( (平面圖平面圖) )上色時(shí)發(fā)上色時(shí)發(fā)現(xiàn)，最少只要四種顏色，就能使得現(xiàn)，最少只要四種顏色，就能使得有相鄰國界的國家涂上不同的顏色有相鄰國界的國家涂上不同的顏色 四色猜想的證明一直沒有解決，四色猜想的證明一直沒有解決，直到一百多年后，在計(jì)算

8、機(jī)出現(xiàn)以直到一百多年后，在計(jì)算機(jī)出現(xiàn)以后，于后，于19761976年用計(jì)算機(jī)算了年用計(jì)算機(jī)算了12001200多多小時(shí)，才證明了四色猜想問題小時(shí)，才證明了四色猜想問題。12 5、又過了半個(gè)世紀(jì) 四色猜想問題出現(xiàn)后，圖論的研四色猜想問題出現(xiàn)后，圖論的研究又停滯了半個(gè)世紀(jì)，直到究又停滯了半個(gè)世紀(jì)，直到19201920年年科尼格科尼格寫了許多關(guān)于圖論方面的論寫了許多關(guān)于圖論方面的論文，并于文，并于19361936年發(fā)表了第一本關(guān)于年發(fā)表了第一本關(guān)于圖論的書。此后圖論從理論上到應(yīng)圖論的書。此后圖論從理論上到應(yīng)用上都有了很大發(fā)展。特別是計(jì)算用上都有了很大發(fā)展。特別是計(jì)算機(jī)的出現(xiàn)使圖論得到飛躍的發(fā)展。機(jī)的

9、出現(xiàn)使圖論得到飛躍的發(fā)展。13 學(xué)好圖論十分重要 圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支如群論、矩陣論、集合論、概率論、拓?fù)鋵W(xué)、數(shù)如群論、矩陣論、集合論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系值分析等有著密切的聯(lián)系 。 圖論給含有二元關(guān)系的系統(tǒng)提供了數(shù)學(xué)模型，圖論給含有二元關(guān)系的系統(tǒng)提供了數(shù)學(xué)模型，因而在許多領(lǐng)域里都具有越來越重要的地位，并因而在許多領(lǐng)域里都具有越來越重要的地位，并且在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取且在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得了豐碩的成果。得了豐碩的成果。 從二十世際從二十世際50 50 年代以來，由于計(jì)算機(jī)的

10、迅速發(fā)年代以來，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，使得圖論成為數(shù)展，有力地推動(dòng)了圖論的發(fā)展，使得圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。學(xué)領(lǐng)域里發(fā)展最快的分支之一。14第第7 7章章 圖的概念圖的概念本章學(xué)習(xí)：本章學(xué)習(xí)：1.1. 無向無向圖及有向圖圖及有向圖2.2. 通路、回路、圖的連通性通路、回路、圖的連通性3.3. 圖的矩陣表示圖的矩陣表示4.4. 最短路徑及關(guān)鍵路徑最短路徑及關(guān)鍵路徑 15今日內(nèi)容無向圖及有向圖無向圖及有向圖圖的一些相關(guān)概念圖的一些相關(guān)概念度度握手定理握手定理子圖相關(guān)概念子圖相關(guān)概念圖同構(gòu)圖同構(gòu)16預(yù)備知識(shí)有序積有序積: A: AB= |xAyBB= |xAyB

11、有序?qū)τ行驅(qū)? : 無序積無序積: A&B= (x,y) |xAyB: A&B= (x,y) |xAyB無序?qū)o序?qū)? (x,y)=(y,x): (x,y)=(y,x)多重集多重集: a,a,a,b,b,ca,b,c: a,a,a,b,b,ca,b,c重復(fù)度重復(fù)度: a: a的重復(fù)度為的重復(fù)度為3, b3, b的為的為2, c2, c的為的為1 1171 1、無序積、無序積：A&BA&B設(shè)設(shè)A A、B B為兩集合，稱為兩集合，稱a,b|aAbBa,b|aAbB為為A A與與B B 的無序積，記作的無序積，記作A&BA&B。為方便起見，將無序?qū)榉?/p>

12、便起見，將無序?qū),ba,b記作記作 ( a, b)( a, b)。 ( a, b)( a, b)(b, a)(b, a)例：例：設(shè)設(shè)A=a,b, B=c,d, A=a,b, B=c,d, 則則A&BA&B？ A&AA&A？ A&B=( a, c), (a,d),( b,c),( b,d)A&B=( a, c), (a,d),( b,c),( b,d) A&A=( a, a ),( a, b),( b, b) A&A=( a, a ),( a, b),( b, b)182 2、無向圖、無向圖一個(gè)一個(gè)無向圖無向圖G G是一個(gè)二元組是

13、一個(gè)二元組,即即G=,G=,其中其中: :. . V V是一個(gè)非空集合是一個(gè)非空集合, ,稱為稱為G G的的頂點(diǎn)集頂點(diǎn)集,V,V中元素中元素稱為稱為頂點(diǎn)頂點(diǎn)或或結(jié)點(diǎn)結(jié)點(diǎn); ;. . E E是無序積是無序積V&VV&V的一個(gè)的一個(gè)多重子集多重子集, ,稱稱E E為為G G的的邊邊集集,E,E中元素稱為中元素稱為無向邊無向邊或簡稱或簡稱邊邊。用小圓圈表示用小圓圈表示V V中頂點(diǎn)中頂點(diǎn), ,若若(a,b)E,(a,b)E,就在就在a,ba,b之間連之間連線段表示邊線段表示邊(a,b),(a,b),其中頂點(diǎn)的位置、連線的曲直及其中頂點(diǎn)的位置、連線的曲直及是否相交都無關(guān)緊要。是否相交都無

14、關(guān)緊要。19無向圖示例 給定無向圖G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). 203 3、有向圖、有向圖 一個(gè)一個(gè)有向圖有向圖D D是一個(gè)二元組是一個(gè)二元組, 即即D = ,D = ,其中：其中： . . V V同無向圖中的頂點(diǎn)集同無向圖中的頂點(diǎn)集; ; . . E E是笛卡兒積的是笛卡兒積的多重子集多重子集, ,其元素稱為其元素稱為有向邊有向邊, ,也簡稱也簡稱邊邊. .21有向圖示例 給定有向圖D=，其中 Va,b,c,d，E,。 22圖的一些概念和規(guī)定G G表示無向圖，但有

15、時(shí)用表示無向圖，但有時(shí)用G G泛指圖泛指圖( (無向的或有向的無向的或有向的) )。D D只能表示有向圖。只能表示有向圖。V(G)V(G)，E(G)E(G)分別表示分別表示G G的頂點(diǎn)集和邊集。的頂點(diǎn)集和邊集。若若| |V(G)|V(G)|n n，則稱則稱G G為為n n階圖階圖。若若| |V(G)|V(G)|與與| |E(G)|E(G)|均為有限數(shù)，則稱均為有限數(shù)，則稱G G為為有限圖有限圖。 若邊集若邊集E(G)E(G)，則稱則稱G G為為零圖零圖，此時(shí)，又若，此時(shí)，又若G G為為n n階圖階圖，則稱，則稱G G為為n n階零圖階零圖，記作，記作N Nn n，特別地，稱特別地，稱N N1

16、1為為平凡圖平凡圖 在圖的定義中規(guī)定頂點(diǎn)集在圖的定義中規(guī)定頂點(diǎn)集V V為非空集，但在圖的運(yùn)算中為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空集的圖為空?qǐng)D空?qǐng)D，并將，并將空?qǐng)D記為空?qǐng)D記為。 23標(biāo)定圖與非標(biāo)定圖、基圖 將圖的集合定義轉(zhuǎn)化成圖形表示之后，將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用常用e ek k表示表示無向邊無向邊( (v vi i,v ,vj j) )（或或有向邊有向邊 ），），并稱頂點(diǎn)或邊用字母標(biāo)定的并稱頂點(diǎn)或邊用字母標(biāo)定的圖為圖為標(biāo)定圖標(biāo)定圖，否則稱為，否則稱為非標(biāo)定圖非標(biāo)定圖。將有向圖各有向邊

17、均改成無向邊后的無將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的向圖稱為原來圖的基圖基圖。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的，任何無向圖的，任何無向圖G G的各邊均加上箭頭就的各邊均加上箭頭就可以得到可以得到以以G G為基圖的有向圖為基圖的有向圖。 24關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn) 設(shè)設(shè)G G為無向圖，為無向圖，ek( (vi, ,vj)E)E，稱稱vi, ,vj為為ek的端點(diǎn)，的端點(diǎn)，ek與與vi或或ek與與vj是是彼此相關(guān)聯(lián)彼此相關(guān)聯(lián)的。的。若若vivj，則稱則稱ek與與vi或或ek與與vj的的關(guān)聯(lián)次數(shù)關(guān)聯(lián)次數(shù)為為1 1。若若vivj，則稱則稱ek與與

18、vi的的關(guān)聯(lián)次數(shù)為關(guān)聯(lián)次數(shù)為2 2，并稱，并稱ek為為環(huán)環(huán)。任意的任意的vlVV，若若vlvi且且vlvj，則稱則稱ek與與vl的的關(guān)關(guān)聯(lián)次數(shù)為聯(lián)次數(shù)為0 0。 25關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn) 設(shè)設(shè)D D為有向圖，為有向圖，ek EE，稱稱vi, ,vj為為ek的的端點(diǎn)端點(diǎn)。若若vivj，則稱則稱ek為為D D中的中的環(huán)環(huán)。無論在無向圖中還是在有向圖中，無邊無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點(diǎn)均稱為關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)孤立點(diǎn)。 26相鄰與鄰接 設(shè)無向圖設(shè)無向圖G GVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et( (vi，vj) )，則稱則稱vi與與vj是彼此相是

19、彼此相鄰的鄰的若若ek與與el至少有一個(gè)公共端點(diǎn)，則稱至少有一個(gè)公共端點(diǎn)，則稱ek與與el是彼此是彼此相鄰的相鄰的。 設(shè)有向圖設(shè)有向圖D DVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et ，則稱則稱vi為為et的始點(diǎn)的始點(diǎn)，vj為為et的終點(diǎn)，并稱的終點(diǎn)，并稱vi鄰接到鄰接到vj，vj鄰接于鄰接于vi。若若ek的終點(diǎn)為的終點(diǎn)為el的始點(diǎn)，則稱的始點(diǎn)，則稱ek與與el相鄰相鄰。27例：點(diǎn)邊之間的關(guān)聯(lián)次數(shù)例：點(diǎn)邊之間的關(guān)聯(lián)次數(shù)28例：點(diǎn)點(diǎn)、邊邊之間的相鄰關(guān)系例：點(diǎn)點(diǎn)、邊邊之間的相鄰關(guān)系29頂點(diǎn)的度數(shù)定義定義 設(shè)設(shè)G G為一無向圖，為一無向圖， vVV，稱稱v作作為邊的端點(diǎn)次數(shù)之

20、和為為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡稱為度的度數(shù)，簡稱為度，記做，記做 dG( (v) )。在不發(fā)生混淆時(shí)，簡記為在不發(fā)生混淆時(shí)，簡記為d( (v) )。設(shè)設(shè)D DVE為有向圖，為有向圖， vVV，稱稱v作為邊的作為邊的始點(diǎn)次數(shù)之和始點(diǎn)次數(shù)之和為為v的的出度出度，記做，記做d+ +D( (v) )，簡記作簡記作d+ +( (v) )。稱稱v作為邊的作為邊的終點(diǎn)次數(shù)之和終點(diǎn)次數(shù)之和為為v的的入度入度，記做，記做 d -D( (v) )，簡記作簡記作d- -( (v) )。稱稱d+ +( (v)+)+d- -( (v) )為為v v的度數(shù)的度數(shù)，記做，記做d( (v) )。30d (v1)=4 d

21、(v2)=4 d(v3)=3 d(v4)=1 d(v5)=0 31d+(v1)=2d+ (v2)=1 d+ (v3)=3 d+ (v4)=1 d+ (v5)=1 d-(v1)=1d- (v2)=3 d- (v3)=0 d- (v4)=3 d- (v5)=1 d (v1)=3d (v2)=4 d (v3)=3 d (v4)=4 d (v5)=2 32最大(出/入)度,最小(出/入)度在無向圖在無向圖G G中中，最大度: (G) = max dG(v) | vV(G) 最小度: (G) = min dG(v) | vV(G) 在有向圖在有向圖D D中，中，最大出度: +(D) = max dD+(

22、v) | vV(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 簡記為, , +, +, -, -33握手定理（圖論基本定理）握手定理（圖論基本定理）定理定理7.1 7.1 設(shè)圖G=為無向圖或有向圖， V = v1, v2, vn,|E|=m，則說明說明任何無向圖中，各頂點(diǎn)度數(shù)之和等于邊數(shù)的兩倍。證明證明G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。 推論：推論：任何圖中，度為奇數(shù)

23、的頂點(diǎn)個(gè)數(shù)為偶數(shù)。 12niid vm34問題研究問題：問題：在一個(gè)部門的25個(gè)人中間，由于意見不同，是否可能每個(gè)人恰好與其他5個(gè)人意見一致？解答：解答：不可能。考慮一個(gè)圖，其中頂點(diǎn)代表人，如果兩個(gè)人意見相同，可用邊連接，所以每個(gè)頂點(diǎn)都是奇數(shù)度。存在奇數(shù)個(gè)度數(shù)為奇數(shù)的圖，這是不可能的。說明：說明：(1)很多離散問題可以用圖模型求解。(2)為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。(3)在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。35握手定理握手定理定理7.2 設(shè)有向圖D=， V = v1, v2, vn,|E|=m，則 11nniiiidvdvm36度數(shù)列設(shè)設(shè)G G為一個(gè)為一個(gè)n階無

24、向圖，階無向圖，V V v1 1, ,v2 2,vn ，稱稱d( (v1 1) )，d( (v2 2) )，d( (vn n) )為為G G的的度數(shù)列度數(shù)列。對(duì)于對(duì)于頂點(diǎn)標(biāo)定頂點(diǎn)標(biāo)定的無向圖，它的度數(shù)列是唯一的。的無向圖，它的度數(shù)列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列反之，對(duì)于給定的非負(fù)整數(shù)列d d1 1, ,d2 2,dn ，若存在若存在V V v1 1, ,v2 2,vn 為頂點(diǎn)集的為頂點(diǎn)集的n階無向圖階無向圖G G，使得使得d( (vi) )di，則稱則稱d是是可圖化可圖化的。的。特別地，若所得圖是簡單圖，則稱特別地，若所得圖是簡單圖，則稱d是是可簡單圖化可簡單圖化的。的。類似地，設(shè)類似

25、地，設(shè)D D為一個(gè)為一個(gè)n n階有向圖，階有向圖，V V v1 1, ,v2 2,vn ，稱稱d( (v1 1) )，d( (v2 2) )，d( (vn) )為為D D的度數(shù)列，的度數(shù)列，另外稱另外稱d+ +( (v1 1) )，d+ +( (v2 2) )，d+ +( (vn) )與與d- -( (v1 1) )，d- -( (v2 2) )，d- -( (vn) )分別為分別為D D的的出度列出度列和和入度列入度列。37度數(shù)列舉例按頂點(diǎn)的標(biāo)定順序，度數(shù)列為 4,4,2,1,3。38度數(shù)列舉例按字母順序，度數(shù)列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,239 (4，4，3，

26、1，0) (3，4，3，4，2)練習(xí)：練習(xí)：40可圖化的充要條件定理 設(shè)非負(fù)整數(shù)列d(d1，d2，dn)，則d是可圖化的當(dāng)且僅當(dāng) n n1)2(mod0iid證明 必要性。由握手定理顯然得證。充分性。由已知條件可知，d中有偶數(shù)個(gè)奇數(shù)度點(diǎn)。奇數(shù)度點(diǎn)兩兩之間連一邊，剩余度用環(huán)來實(shí)現(xiàn)。533141例例7.17.1： (3, 3, 2, 3), (5, 2, 3, 1, 4)(3, 3, 2, 3), (5, 2, 3, 1, 4)能成為圖的度能成為圖的度數(shù)序列嗎？為什么？數(shù)序列嗎？為什么？ 已知圖已知圖G G中有中有1010條邊，條邊，4 4個(gè)個(gè)3 3度頂點(diǎn)，其余頂點(diǎn)的度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于等

27、于度數(shù)均小于等于2 2，問，問G G中至少有多少個(gè)頂點(diǎn)？為中至少有多少個(gè)頂點(diǎn)？為什么？什么？解：解：1.1.由于這兩個(gè)序列中，奇數(shù)度頂點(diǎn)個(gè)數(shù)均為奇數(shù)，由于這兩個(gè)序列中，奇數(shù)度頂點(diǎn)個(gè)數(shù)均為奇數(shù)，由握手定理的推論可知，它們都不能成為圖的度由握手定理的推論可知，它們都不能成為圖的度數(shù)序列。數(shù)序列。2.2.顯然，顯然，圖圖G中的其余頂點(diǎn)度數(shù)均為中的其余頂點(diǎn)度數(shù)均為2時(shí)時(shí)G圖的頂點(diǎn)圖的頂點(diǎn)數(shù)最少數(shù)最少. 設(shè)設(shè)G圖至少有圖至少有x個(gè)頂點(diǎn)個(gè)頂點(diǎn). 由握手定理可知，由握手定理可知， 34+2(x-4)=2 10 解得解得: x=8 所以所以G至少有至少有8個(gè)頂點(diǎn)。個(gè)頂點(diǎn)。42簡單圖與多重圖 定義定義 在在無向

28、圖無向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無向邊如果多于中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無向邊如果多于1 1條條，則稱這些邊為，則稱這些邊為平行邊平行邊，平行邊的條數(shù)稱為，平行邊的條數(shù)稱為重?cái)?shù)重?cái)?shù)。在在有向圖有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1 1條，條，并且這些邊的始點(diǎn)和終點(diǎn)相同并且這些邊的始點(diǎn)和終點(diǎn)相同( (也就是它們的方向相也就是它們的方向相同同) )，則稱這些邊為，則稱這些邊為平行邊平行邊。含平行邊的圖稱為含平行邊的圖稱為多重圖多重圖。既不含平行邊也不含環(huán)的圖稱為既不含平行邊也不含環(huán)的圖稱為簡單圖簡單圖。43簡單圖與多重圖示例 44完全圖定義定義7 7. .7 7 設(shè)G為n階無向

29、簡單圖，若G中每個(gè)頂點(diǎn)均與其余的n-1個(gè)頂點(diǎn)相鄰，則稱G為n階無向完全圖，簡稱n階完全圖階完全圖，記做Kn(n1)。 設(shè)D為n階有向簡單圖，若D中每個(gè)頂點(diǎn)都鄰接到其余的n-1個(gè)頂點(diǎn)，又鄰接于其余的n-1個(gè)頂點(diǎn)，則稱D是n階有向完全圖階有向完全圖。設(shè)D為n階有向簡單圖，若D的基圖為n階無向完全圖Kn，則稱D是n階競賽圖階競賽圖。45完全圖舉例n階無向完全圖的邊數(shù)為：階無向完全圖的邊數(shù)為：n( (n-1)/2-1)/2n階有向完全圖的邊數(shù)為：階有向完全圖的邊數(shù)為：n( (n-1)-1)n階競賽圖的邊數(shù)為：階競賽圖的邊數(shù)為： n( (n-1)/2-1)/2K53階有向完全圖4階競賽圖46正則圖定義定

30、義設(shè)設(shè)G G為為n階無向簡單圖，若階無向簡單圖，若vV(G)V(G)，均有均有d( (v) )k，則稱則稱G G為為k- -正則圖正則圖。 舉例舉例 n階零圖是階零圖是0- 0-正則圖正則圖n階無向完全圖是階無向完全圖是( (n-1)-1)-正則圖正則圖彼得森圖是彼得森圖是3- 3-正則圖正則圖說明說明 n階階k- -正則圖中，邊數(shù)正則圖中，邊數(shù)mkn/2/2。當(dāng)當(dāng)k為奇數(shù)時(shí)，為奇數(shù)時(shí)，n必為偶數(shù)。必為偶數(shù)。47子圖定義定義設(shè)設(shè)G ，G 為兩個(gè)圖為兩個(gè)圖( (同為無向圖同為無向圖或同為有向圖或同為有向圖) )，若，若V V且且E E，則稱則稱G G 是是G G的的子子圖圖，G為為G 的的母圖母

31、圖，記作，記作G G。若若V V或或E E，則稱則稱G 為為G的的真子圖真子圖。若若V V，則稱則稱G 為為G的的生成子圖生成子圖。 設(shè)設(shè)G 為一圖，為一圖，V1 1 V且且V1 1，稱以稱以V1 1為頂為頂點(diǎn)集，以點(diǎn)集，以G中兩個(gè)端點(diǎn)都在中兩個(gè)端點(diǎn)都在V1 1中的邊組成邊集中的邊組成邊集E1 1的的圖為圖為G的的V1 1導(dǎo)出的子圖導(dǎo)出的子圖，記作，記作G V1 1 。設(shè)設(shè)E1 1 E且且E1 1，稱以稱以E1 1為邊集，以為邊集，以E1 1中邊關(guān)聯(lián)的中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集頂點(diǎn)為頂點(diǎn)集V1 1的圖為的圖為G的的E1 1導(dǎo)出的子圖導(dǎo)出的子圖，記作，記作G E1 1 。48在上圖中，在上圖中，(2

32、)，(3)均為均為(1)的子圖；的子圖；(3)是生成子圖；是生成子圖；(5)，(6)均為均為(4)的子圖；的子圖；(5)是生成子圖；是生成子圖；49導(dǎo)出子圖舉例在上圖中，設(shè)在上圖中，設(shè)G G為為(1)(1)中圖所表示，中圖所表示，取取V V1 1a,b,ca,b,c，則則V V1 1的導(dǎo)出子圖的導(dǎo)出子圖GVGV1 1 為為(2)(2)中圖中圖所示。所示。取取E E1 1ee1 1,e ,e3 3 ，則則E E1 1的導(dǎo)出子圖的導(dǎo)出子圖GEGE1 1 為為(3)(3)中圖中圖所示。所示。50補(bǔ)圖定義7.9 設(shè)G為n階無向簡單圖，以V為頂點(diǎn)集，以所有為邊集使G成為完全圖Kn的添加邊組成的集合的圖，稱為G的補(bǔ)圖，記作G。若圖GG，則稱為G是自補(bǔ)圖。(1)(1)為自補(bǔ)圖為自補(bǔ)圖(2)(2)和和(3)(3)互為補(bǔ)圖互為補(bǔ)圖51在下圖中，在下圖中，(1)是是(2)的補(bǔ)圖，