有向圖與無向圖

1、離散數(shù)學(xué),CH7 圖的基本概念 1無向圖及有向圖,1,圖論的起源,圖論是組合數(shù)學(xué)的一個(gè)分支,它起源于1736年歐拉的第一篇關(guān)于圖論的論文，這篇論文解決了著名的 “哥尼斯堡七橋問題” ，從而使歐拉成為圖論的創(chuàng)始人。,1.哥尼斯堡七橋問題,哥尼斯堡位于前蘇聯(lián)的加里寧格勒，歷史上曾經(jīng)是德國東普魯士省的省會，普雷格爾河橫穿城堡，河中有兩個(gè)小島，共有七座橋連接兩岸和小島。 問題： 在所有橋都只能走一遍的前提下，如何才能把這個(gè)地方所有的橋都走遍？,哥尼斯堡七橋問題解決方式,萊昂哈德歐拉（Leonhard Euler）在1735年圓滿地解決了這一問題，證明這種方法并不存在，也順帶解決了一筆畫問題。他在圣彼得

2、堡科學(xué)院發(fā)表了圖論史上第一篇重要文獻(xiàn)。歐拉把實(shí)際的抽象問題簡化為平面上的點(diǎn)與線組合，每一座橋視為一條線，橋所連接的地區(qū)視為點(diǎn)。這樣若從某點(diǎn)出發(fā)后最后再回到這點(diǎn)，則這一點(diǎn)的線數(shù)必須是偶數(shù)。, ,圖論的起源,歐拉最后給出任意一種河橋圖能否全部走一次的判定法則。如果通奇數(shù)座橋的地方不止兩個(gè)，那么滿足要求的路線便不存在了。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若沒有一個(gè)地方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn)，他還說明了怎樣快速找到所要求的路線。 不少數(shù)學(xué)家都嘗試去解析這個(gè)事例。而這些解析，最后發(fā)展成為了數(shù)學(xué)中的圖論。,5,歐 拉 圖,定義 一個(gè)圖,如果能夠從

3、一點(diǎn)出發(fā),經(jīng)過每條邊一次且僅一次再回到起點(diǎn),則稱為歐拉圖 歐拉在論文中給出并證明了判斷歐拉圖的充分必要條件定理,并證明了七橋圖不是歐拉圖。,從這個(gè)問題可以看出：,圖：圖用點(diǎn)代表各個(gè)事物,用邊代表各個(gè)事物間的二元關(guān)系。 所以，圖是研究集合上的二元關(guān)系的工具，是建立數(shù)學(xué)模型的一個(gè)重要手段。,2、一百多年以后,“七橋”問題以后，圖論的研究停滯了一百多年，直到1847年，基爾霍夫用“樹”圖解決了電路理論中的求解聯(lián)立方程的問題，十年后凱萊用 “樹” 圖計(jì)算有機(jī)化學(xué)中的問題。在這一時(shí)期流行著兩個(gè)著名的圖論問題：哈密爾頓回路問題和 “四色猜想” 問題。,3.哈密爾頓回路問題,1856年,英國數(shù)學(xué)家哈密爾頓設(shè)

4、計(jì)了一個(gè)周游世界的游戲，他在一個(gè)正十二面體的二十個(gè)頂點(diǎn)上標(biāo)上二十個(gè)著名城市的名字，要求游戲者從一個(gè)城市出發(fā)，經(jīng)過每一個(gè)城市一次且僅一次，然后回到出發(fā)點(diǎn)。,哈密爾頓回路圖,此路線稱為：哈密爾頓回路， 而此圖稱為：哈密爾頓圖。,4、“四 色 猜 想” 問 題,人們在長期為地圖(平面圖)上色時(shí)發(fā)現(xiàn)，最少只要四種顏色，就能使得有相鄰國界的國家涂上不同的顏色 四色猜想的證明一直沒有解決，直到一百多年后，在計(jì)算機(jī)出現(xiàn)以后，于1976年用計(jì)算機(jī)算了1200多小時(shí)，才證明了四色猜想問題。,5、又過了半個(gè)世紀(jì),四色猜想問題出現(xiàn)后，圖論的研究又停滯了半個(gè)世紀(jì)，直到1920年科尼格寫了許多關(guān)于圖論方面的論文，并于1

5、936年發(fā)表了第一本關(guān)于圖論的書。此后圖論從理論上到應(yīng)用上都有了很大發(fā)展。特別是計(jì)算機(jī)的出現(xiàn)使圖論得到飛躍的發(fā)展。,學(xué)好圖論十分重要,圖論是組合數(shù)學(xué)的一個(gè)分支，與其它數(shù)學(xué)分支如群論、矩陣論、集合論、概率論、拓?fù)鋵W(xué)、數(shù)值分析等有著密切的聯(lián)系 。 圖論給含有二元關(guān)系的系統(tǒng)提供了數(shù)學(xué)模型，因而在許多領(lǐng)域里都具有越來越重要的地位，并且在物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)等各方面都取得了豐碩的成果。 從二十世際50 年代以來，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動了圖論的發(fā)展，使得圖論成為數(shù)學(xué)領(lǐng)域里發(fā)展最快的分支之一。,第7章 圖的概念 本章學(xué)習(xí)： 1. 無向圖及有向圖 2. 通路、回路、圖的連通性 3. 圖的矩陣表

6、示 4. 最短路徑及關(guān)鍵路徑,14,今日內(nèi)容,無向圖及有向圖 圖的一些相關(guān)概念 度 握手定理 子圖相關(guān)概念 圖同構(gòu),15,預(yù)備知識,有序積: AB= |xAyB 有序?qū)? 無序積: A . E是無序積V . E是笛卡兒積的多重子集,其元素稱為有向邊,也簡稱邊.,20,有向圖示例,給定有向圖D=，其中 Va,b,c,d， E, , , ,。,圖的一些概念和規(guī)定,G表示無向圖，但有時(shí)用G泛指圖(無向的或有向的)。 D只能表示有向圖。 V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。 若|V(G)|n，則稱G為n階圖。 若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。 若邊集E(G)，則稱G為零

7、圖，此時(shí)，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖 在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空圖，并將空圖記為。,標(biāo)定圖與非標(biāo)定圖、基圖,將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有向邊），并稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。 將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。 易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。,關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn),設(shè)G為無向圖，ek(vi,vj)E， 稱vi,vj

8、為ek的端點(diǎn)，ek與vi或ek與vj是彼此相關(guān)聯(lián)的。 若vivj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1。 若vivj，則稱ek與vi的關(guān)聯(lián)次數(shù)為2，并稱ek為環(huán)。 任意的vlV，若vlvi且vlvj，則稱ek與vl的關(guān)聯(lián)次數(shù)為0。,關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn),設(shè)D為有向圖，ekE，稱vi,vj為ek的端點(diǎn)。 若vivj，則稱ek為D中的環(huán)。 無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)。,相鄰與鄰接,設(shè)無向圖G，vi，vjV，ek，elE。 若etE，使得et(vi，vj)，則稱vi與vj是彼此相鄰的 若ek與el至少有一個(gè)公共端點(diǎn)，則稱ek與el是彼此相鄰的。 設(shè)有向圖D，v

9、i，vjV，ek，elE。 若etE，使得et，則稱vi為et的始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi。 若ek的終點(diǎn)為el的始點(diǎn)，則稱ek與el相鄰。,例：點(diǎn)邊之間的關(guān)聯(lián)次數(shù),27,例：點(diǎn)點(diǎn)、邊邊之間的相鄰關(guān)系,28,頂點(diǎn)的度數(shù),定義 設(shè)G為一無向圖，vV，稱v作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡稱為度，記做 dG(v)。 在不發(fā)生混淆時(shí)，簡記為d(v)。 設(shè)D為有向圖，vV， 稱v作為邊的始點(diǎn)次數(shù)之和為v的出度，記做d+D(v)，簡記作d+(v)。 稱v作為邊的終點(diǎn)次數(shù)之和為v的入度，記做 d -D(v)，簡記作d-(v)。 稱d+(v)+d-(v)為v的度數(shù)，記做d(v

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

11、x dD+(v) | vV(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 簡記為, , +, +, -, -,32,握手定理（圖論基本定理）,定理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ù)的頂點(diǎn)個(gè)數(shù)為偶數(shù)。,33,問

12、題研究,問題：在一個(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)系。,握手定理,定理7.2 設(shè)有向圖D=， V = v1, v2, vn,|E|=m，則,35,度數(shù)列,設(shè)G為一個(gè)n階無向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為G的度數(shù)列。 對于頂點(diǎn)標(biāo)定的

13、無向圖，它的度數(shù)列是唯一的。 反之，對于給定的非負(fù)整數(shù)列dd1,d2,dn，若存在Vv1,v2,vn為頂點(diǎn)集的n階無向圖G，使得d(vi)di，則稱d是可圖化的。 特別地，若所得圖是簡單圖，則稱d是可簡單圖化的。 類似地，設(shè)D為一個(gè)n階有向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，d+(vn)與d-(v1)，d-(v2)，d-(vn)分別為D的出度列和入度列。,度數(shù)列舉例,按頂點(diǎn)的標(biāo)定順序，度數(shù)列為4,4,2,1,3。,度數(shù)列舉例,按字母順序， 度數(shù)列：5,3,3,3 出度列：4,0,2,1 入度列：1,3,1,2,(4，4，3

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

15、時(shí)G圖的頂點(diǎn)數(shù)最少. 設(shè)G圖至少有x個(gè)頂點(diǎn). 由握手定理可知， 34+2(x-4)=2 10 解得: x=8 所以G至少有8個(gè)頂點(diǎn)。,41,簡單圖與多重圖,定義 在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。 在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊如果多于1條，并且這些邊的始點(diǎn)和終點(diǎn)相同(也就是它們的方向相同)，則稱這些邊為平行邊。 含平行邊的圖稱為多重圖。 既不含平行邊也不含環(huán)的圖稱為簡單圖。,43,簡單圖與多重圖示例,完全圖,定義7.7 設(shè)G為n階無向簡單圖，若G中每個(gè)頂點(diǎn)均與其余的n-1個(gè)頂點(diǎn)相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記做Kn(n1

16、)。 設(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階競賽圖。,完全圖舉例,n階無向完全圖的邊數(shù)為：n(n-1)/2 n階有向完全圖的邊數(shù)為：n(n-1) n階競賽圖的邊數(shù)為： n(n-1)/2,K5,3階有向完全圖,4階競賽圖,正則圖,定義設(shè)G為n階無向簡單圖，若vV(G)，均有d(v)k，則稱G為k-正則圖。 舉例n階零圖是0-正則圖 n階無向完全圖是(n-1)-正則圖 彼得森圖是3-正則圖 說明n階k-正則圖中，邊數(shù)mkn/2。 當(dāng)k為奇數(shù)時(shí)，n必為偶數(shù)

17、。,子圖,定義設(shè)G，G為兩個(gè)圖(同為無向圖或同為有向圖)，若V V且E E，則稱G是G的子圖，G為G 的母圖，記作G G。 若V V或E E，則稱G 為G的真子圖。 若V V，則稱G 為G的生成子圖。 設(shè)G為一圖，V1V且V1，稱以V1為頂點(diǎn)集，以G中兩個(gè)端點(diǎn)都在V1中的邊組成邊集E1的圖為G的V1導(dǎo)出的子圖，記作GV1。 設(shè)E1E且E1，稱以E1為邊集，以E1中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集V1的圖為G的E1導(dǎo)出的子圖，記作GE1。,在上圖中，(2)，(3)均為(1)的子圖；(3)是生成子圖；,(5)，(6)均為(4)的子圖；(5)是生成子圖；,48,導(dǎo)出子圖舉例,在上圖中，設(shè)G為(1)中圖所表示，

18、取V1a,b,c，則V1的導(dǎo)出子圖GV1為(2)中圖所示。 取E1e1,e3，則E1的導(dǎo)出子圖GE1為(3)中圖所示。,補(bǔ)圖,定義7.9 設(shè)G為n階無向簡單圖，以V為頂點(diǎn)集，以所有為邊集使G成為完全圖Kn的添加邊組成的集合的圖，稱為G的補(bǔ)圖，記作G。 若圖GG，則稱為G是自補(bǔ)圖。,(1)為自補(bǔ)圖 (2)和(3)互為補(bǔ)圖,在下圖中，(1)是(2)的補(bǔ)圖，當(dāng)然(2)也是(1)的補(bǔ)圖，就是說，(1)，(2)互為補(bǔ)圖。同樣，(3)，(4)互為補(bǔ)圖。,51,圖的同構(gòu),在圖論的研究中，我們更關(guān)心的是圖的結(jié)構(gòu), 而這種結(jié)構(gòu)與頂點(diǎn)與邊的具體元素或與圖的圖形的畫法無關(guān). 對此, 我們引進(jìn)同構(gòu)的概念.,52,圖同構(gòu)(graph isomorphism),定義7.10 : 設(shè)兩個(gè)無向（有向）圖G1=, G2=, 若存在雙射f:V1V2, 滿足 uV1,vV1, e=(u,v)E1 e=(f(u),f(v)E2 (e=E1 e=E2 ) 并且e與e的重?cái)?shù)相同， 則稱G1與G2同構(gòu), 記作G1G2 說明: 同構(gòu)的圖,其圖論