圖基本概念無向圖以及有向圖

1、關于圖的基本概念無向圖及有向圖第一張，PPT共六十一頁，創(chuàng)作于2022年6月 圖論的起源圖論是組合數學的一個分支,它起源于1736年歐拉的第一篇關于圖論的論文，這篇論文解決了著名的 “哥尼斯堡七橋問題” ，從而使歐拉成為圖論的創(chuàng)始人。第二張，PPT共六十一頁，創(chuàng)作于2022年6月1.哥尼斯堡七橋問題 哥尼斯堡位于前蘇聯(lián)的加里寧格勒，歷史上曾經是德國東普魯士省的省會，普雷格爾河橫穿城堡，河中有兩個小島，共有七座橋連接兩岸和小島。 問題： 在所有橋都只能走一遍的前提下，如何才能把這個地方所有的橋都走遍？第三張，PPT共六十一頁，創(chuàng)作于2022年6月哥尼斯堡七橋問題解決方式萊昂哈德歐拉（Leonha

2、rd Euler）在1735年圓滿地解決了這一問題，證明這種方法并不存在，也順帶解決了一筆畫問題。他在圣彼得堡科學院發(fā)表了圖論史上第一篇重要文獻。歐拉把實際的抽象問題簡化為平面上的點與線組合，每一座橋視為一條線，橋所連接的地區(qū)視為點。這樣若從某點出發(fā)后最后再回到這點，則這一點的線數必須是偶數。 /wiki/File:Konigsberg_bridges.png 第四張，PPT共六十一頁，創(chuàng)作于2022年6月5圖論的起源歐拉最后給出任意一種河橋圖能否全部走一次的判定法則。如果通奇數座橋的地方不止兩個，那么滿足要求的路線便不存在了。如果只有兩個地方通奇數座橋，則可從

3、其中任何一地出發(fā)找到所要求的路線。若沒有一個地方通奇數座橋，則從任何一地出發(fā)，所求的路線都能實現，他還說明了怎樣快速找到所要求的路線。不少數學家都嘗試去解析這個事例。而這些解析，最后發(fā)展成為了數學中的圖論。第五張，PPT共六十一頁，創(chuàng)作于2022年6月 歐 拉 圖定義 一個圖,如果能夠從一點出發(fā),經過每條邊一次且僅一次再回到起點,則稱為歐拉圖 歐拉在論文中給出并證明了判斷歐拉圖的充分必要條件定理,并證明了七橋圖不是歐拉圖。第六張，PPT共六十一頁，創(chuàng)作于2022年6月 從這個問題可以看出：圖：圖用點代表各個事物,用邊代表各個事物間的二元關系。 所以，圖是研究集合上的二元關系的工具，是建立數學模

4、型的一個重要手段。第七張，PPT共六十一頁，創(chuàng)作于2022年6月 2、一百多年以后 “七橋”問題以后，圖論的研究停滯了一百多年，直到1847年，基爾霍夫用“樹”圖解決了電路理論中的求解聯(lián)立方程的問題，十年后凱萊用 “樹” 圖計算有機化學中的問題。在這一時期流行著兩個著名的圖論問題：哈密爾頓回路問題和 “四色猜想” 問題。第八張，PPT共六十一頁，創(chuàng)作于2022年6月3.哈密爾頓回路問題 1856年,英國數學家哈密爾頓設計了一個周游世界的游戲，他在一個正十二面體的二十個頂點上標上二十個著名城市的名字，要求游戲者從一個城市出發(fā)，經過每一個城市一次且僅一次，然后回到出發(fā)點。第九張，PPT共六十一頁，

5、創(chuàng)作于2022年6月哈密爾頓回路圖 此路線稱為：哈密爾頓回路， 而此圖稱為：哈密爾頓圖。第十張，PPT共六十一頁，創(chuàng)作于2022年6月4、“四 色 猜 想” 問 題 人們在長期為地圖(平面圖)上色時發(fā)現，最少只要四種顏色，就能使得有相鄰國界的國家涂上不同的顏色 四色猜想的證明一直沒有解決，直到一百多年后，在計算機出現以后，于1976年用計算機算了1200多小時，才證明了四色猜想問題。第十一張，PPT共六十一頁，創(chuàng)作于2022年6月 5、又過了半個世紀 四色猜想問題出現后，圖論的研究又停滯了半個世紀，直到1920年科尼格寫了許多關于圖論方面的論文，并于1936年發(fā)表了第一本關于圖論的書。此后圖論

6、從理論上到應用上都有了很大發(fā)展。特別是計算機的出現使圖論得到飛躍的發(fā)展。第十二張，PPT共六十一頁，創(chuàng)作于2022年6月 學好圖論十分重要 圖論是組合數學的一個分支，與其它數學分支如群論、矩陣論、集合論、概率論、拓撲學、數值分析等有著密切的聯(lián)系 。 圖論給含有二元關系的系統(tǒng)提供了數學模型，因而在許多領域里都具有越來越重要的地位，并且在物理、化學、信息學、運籌學等各方面都取得了豐碩的成果。 從二十世際50 年代以來，由于計算機的迅速發(fā)展，有力地推動了圖論的發(fā)展，使得圖論成為數學領域里發(fā)展最快的分支之一。第十三張，PPT共六十一頁，創(chuàng)作于2022年6月14第7章 圖的概念本章學習：1. 無向圖及有

7、向圖2. 通路、回路、圖的連通性3. 圖的矩陣表示4. 最短路徑及關鍵路徑 第十四張，PPT共六十一頁，創(chuàng)作于2022年6月15今日內容無向圖及有向圖圖的一些相關概念度握手定理子圖相關概念圖同構第十五張，PPT共六十一頁，創(chuàng)作于2022年6月16預備知識有序積: AB= |xAyB有序對: 無序積: A&B= (x,y) |xAyB無序對: (x,y)=(y,x)多重集: a,a,a,b,b,ca,b,c重復度: a的重復度為3, b的為2, c的為1第十六張，PPT共六十一頁，創(chuàng)作于2022年6月171、無序積：A&B設A、B為兩集合，稱a,b|aAbB為A與B 的無序積，記作A&B。為方便

8、起見，將無序對a,b記作 ( a, b)。 ( a, b)(b, a)例：設A=a,b, B=c,d, 則A&B？ A&A？ A&B=( a, c), (a,d),( b,c),( b,d) A&A=( a, a ),( a, b),( b, b)第十七張，PPT共六十一頁，創(chuàng)作于2022年6月182、無向圖一個無向圖G是一個二元組,即G=,其中:. V是一個非空集合,稱為G的頂點集,V中元素稱為頂點或結點;. E是無序積V&V的一個多重子集,稱E為G的邊集,E中元素稱為無向邊或簡稱邊。用小圓圈表示V中頂點,若(a,b)E,就在a,b之間連線段表示邊(a,b),其中頂點的位置、連線的曲直及是否

9、相交都無關緊要。第十八張，PPT共六十一頁，創(chuàng)作于2022年6月無向圖示例 給定無向圖G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). 第十九張，PPT共六十一頁，創(chuàng)作于2022年6月203、有向圖 一個有向圖D是一個二元組, 即D = ,其中： . V同無向圖中的頂點集; . E是笛卡兒積的多重子集,其元素稱為有向邊,也簡稱邊.第二十張，PPT共六十一頁，創(chuàng)作于2022年6月有向圖示例 給定有向圖D=，其中 Va,b,c,d，E,。 第二十一張，PPT共六十一頁，創(chuàng)作于2022年6月

10、圖的一些概念和規(guī)定G表示無向圖，但有時用G泛指圖(無向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點集和邊集。若|V(G)|n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數，則稱G為有限圖。 若邊集E(G)，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖 在圖的定義中規(guī)定頂點集V為非空集，但在圖的運算中可能產生頂點集為空集的運算結果，為此規(guī)定頂點集為空集的圖為空圖，并將空圖記為。 第二十二張，PPT共六十一頁，創(chuàng)作于2022年6月標定圖與非標定圖、基圖 將圖的集合定義轉化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有

11、向邊），并稱頂點或邊用字母標定的圖為標定圖，否則稱為非標定圖。將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。易知標定圖與非標定圖是可以相互轉化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。 第二十三張，PPT共六十一頁，創(chuàng)作于2022年6月關聯(lián)與關聯(lián)次數、環(huán)、孤立點 設G為無向圖，ek(vi,vj)E，稱vi,vj為ek的端點，ek與vi或ek與vj是彼此相關聯(lián)的。若vivj，則稱ek與vi或ek與vj的關聯(lián)次數為1。若vivj，則稱ek與vi的關聯(lián)次數為2，并稱ek為環(huán)。任意的vlV，若vlvi且vlvj，則稱ek與vl的關聯(lián)次數為0。 第二十四張，PPT共六十一頁

12、，創(chuàng)作于2022年6月關聯(lián)與關聯(lián)次數、環(huán)、孤立點 設D為有向圖，ekE，稱vi,vj為ek的端點。若vivj，則稱ek為D中的環(huán)。無論在無向圖中還是在有向圖中，無邊關聯(lián)的頂點均稱為孤立點。 第二十五張，PPT共六十一頁，創(chuàng)作于2022年6月相鄰與鄰接 設無向圖G，vi，vjV，ek，elE。若etE，使得et(vi，vj)，則稱vi與vj是彼此相鄰的若ek與el至少有一個公共端點，則稱ek與el是彼此相鄰的。 設有向圖D，vi，vjV，ek，elE。若etE，使得et，則稱vi為et的始點，vj為et的終點，并稱vi鄰接到vj，vj鄰接于vi。若ek的終點為el的始點，則稱ek與el相鄰。第二

13、十六張，PPT共六十一頁，創(chuàng)作于2022年6月27例：點邊之間的關聯(lián)次數第二十七張，PPT共六十一頁，創(chuàng)作于2022年6月28例：點點、邊邊之間的相鄰關系第二十八張，PPT共六十一頁，創(chuàng)作于2022年6月頂點的度數定義 設G為一無向圖，vV，稱v作為邊的端點次數之和為v的度數，簡稱為度，記做 dG(v)。在不發(fā)生混淆時，簡記為d(v)。設D為有向圖，vV，稱v作為邊的始點次數之和為v的出度，記做d+D(v)，簡記作d+(v)。稱v作為邊的終點次數之和為v的入度，記做 d -D(v)，簡記作d-(v)。稱d+(v)+d-(v)為v的度數，記做d(v)。第二十九張，PPT共六十一頁，創(chuàng)作于2022

14、年6月30d (v1)=4 d(v2)=4 d(v3)=3 d(v4)=1 d(v5)=0 第三十張，PPT共六十一頁，創(chuàng)作于2022年6月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 第三十一張，PPT共六十一頁，創(chuàng)作于2022年6月32最大(出/入)度,最小(出/入)度在無向圖G中，最大度: (G) = max dG(v) | vV(G) 最小度: (G)

15、 = min dG(v) | vV(G) 在有向圖D中，最大出度: +(D) = max dD+(v) | vV(D) 最小出度: +(D) = min dD+(v) | vV(D) 最大入度: -(D) = max dD-(v) | vV(D) 最小入度: -(D) = min dD-(v) | vV(D) 簡記為, , +, +, -, -第三十二張，PPT共六十一頁，創(chuàng)作于2022年6月33握手定理（圖論基本定理）定理7.1 設圖G=為無向圖或有向圖， V = v1, v2, vn,|E|=m，則說明任何無向圖中，各頂點度數之和等于邊數的兩倍。證明G中每條邊(包括環(huán))均有兩個端點，所以在

16、計算G中各頂點度數之和時，每條邊均提供2度，當然，m條邊，共提供2m度。 推論：任何圖中，度為奇數的頂點個數為偶數。 第三十三張，PPT共六十一頁，創(chuàng)作于2022年6月問題研究問題：在一個部門的25個人中間，由于意見不同，是否可能每個人恰好與其他5個人意見一致？解答：不可能?？紤]一個圖，其中頂點代表人，如果兩個人意見相同，可用邊連接，所以每個頂點都是奇數度。存在奇數個度數為奇數的圖，這是不可能的。說明：(1)很多離散問題可以用圖模型求解。(2)為了建立一個圖模型，需要決定頂點和邊分別代表什么。(3)在一個圖模型中，邊經常代表兩個頂點之間的關系。第三十四張，PPT共六十一頁，創(chuàng)作于2022年6月

17、35握手定理定理7.2 設有向圖D=， V = v1, v2, vn,|E|=m，則 第三十五張，PPT共六十一頁，創(chuàng)作于2022年6月度數列設G為一個n階無向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為G的度數列。對于頂點標定的無向圖，它的度數列是唯一的。反之，對于給定的非負整數列dd1,d2,dn，若存在Vv1,v2,vn為頂點集的n階無向圖G，使得d(vi)di，則稱d是可圖化的。特別地，若所得圖是簡單圖，則稱d是可簡單圖化的。類似地，設D為一個n階有向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為D的度數列，另外稱d+(v1)，d+(v2)，d+(vn

18、)與d-(v1)，d-(v2)，d-(vn)分別為D的出度列和入度列。第三十六張，PPT共六十一頁，創(chuàng)作于2022年6月度數列舉例按頂點的標定順序，度數列為4,4,2,1,3。第三十七張，PPT共六十一頁，創(chuàng)作于2022年6月度數列舉例按字母順序，度數列：5,3,3,3出度列：4,0,2,1入度列：1,3,1,2第三十八張，PPT共六十一頁，創(chuàng)作于2022年6月39 (4，4，3，1，0) (3，4，3，4，2)練習：第三十九張，PPT共六十一頁，創(chuàng)作于2022年6月可圖化的充要條件定理 設非負整數列d(d1，d2，dn)，則d是可圖化的當且僅當 證明必要性。由握手定理顯然得證。充分性。由已知

19、條件可知，d中有偶數個奇數度點。奇數度點兩兩之間連一邊，剩余度用環(huán)來實現。5331第四十張，PPT共六十一頁，創(chuàng)作于2022年6月41例7.1：(3, 3, 2, 3), (5, 2, 3, 1, 4)能成為圖的度數序列嗎？為什么？ 已知圖G中有10條邊，4個3度頂點，其余頂點的度數均小于等于2，問G中至少有多少個頂點？為什么？解：1.由于這兩個序列中，奇數度頂點個數均為奇數，由握手定理的推論可知，它們都不能成為圖的度數序列。2.顯然，圖G中的其余頂點度數均為2時G圖的頂點數最少. 設G圖至少有x個頂點. 由握手定理可知， 34+2(x-4)=2 10 解得: x=8 所以G至少有8個頂點。第

20、四十一張，PPT共六十一頁，創(chuàng)作于2022年6月簡單圖與多重圖 定義 在無向圖中，關聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數稱為重數。在有向圖中，關聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。含平行邊的圖稱為多重圖。既不含平行邊也不含環(huán)的圖稱為簡單圖。第四十二張，PPT共六十一頁，創(chuàng)作于2022年6月43簡單圖與多重圖示例 第四十三張，PPT共六十一頁，創(chuàng)作于2022年6月完全圖定義7.7 設G為n階無向簡單圖，若G中每個頂點均與其余的n-1個頂點相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記做Kn(n1)。

21、 設D為n階有向簡單圖，若D中每個頂點都鄰接到其余的n-1個頂點，又鄰接于其余的n-1個頂點，則稱D是n階有向完全圖。設D為n階有向簡單圖，若D的基圖為n階無向完全圖Kn，則稱D是n階競賽圖。第四十四張，PPT共六十一頁，創(chuàng)作于2022年6月完全圖舉例n階無向完全圖的邊數為：n(n-1)/2n階有向完全圖的邊數為：n(n-1)n階競賽圖的邊數為： n(n-1)/2K53階有向完全圖4階競賽圖第四十五張，PPT共六十一頁，創(chuàng)作于2022年6月正則圖定義設G為n階無向簡單圖，若vV(G)，均有d(v)k，則稱G為k-正則圖。 舉例n階零圖是0-正則圖n階無向完全圖是(n-1)-正則圖彼得森圖是3-

22、正則圖說明n階k-正則圖中，邊數mkn/2。當k為奇數時，n必為偶數。第四十六張，PPT共六十一頁，創(chuàng)作于2022年6月子圖定義設G，G為兩個圖(同為無向圖或同為有向圖)，若V V且E E，則稱G是G的子圖，G為G 的母圖，記作G G。若V V或E E，則稱G 為G的真子圖。若V V，則稱G 為G的生成子圖。 設G為一圖，V1V且V1，稱以V1為頂點集，以G中兩個端點都在V1中的邊組成邊集E1的圖為G的V1導出的子圖，記作GV1。設E1E且E1，稱以E1為邊集，以E1中邊關聯(lián)的頂點為頂點集V1的圖為G的E1導出的子圖，記作GE1。第四十七張，PPT共六十一頁，創(chuàng)作于2022年6月48在上圖中，

23、(2)，(3)均為(1)的子圖；(3)是生成子圖；(5)，(6)均為(4)的子圖；(5)是生成子圖；第四十八張，PPT共六十一頁，創(chuàng)作于2022年6月導出子圖舉例在上圖中，設G為(1)中圖所表示，取V1a,b,c，則V1的導出子圖GV1為(2)中圖所示。取E1e1,e3，則E1的導出子圖GE1為(3)中圖所示。第四十九張，PPT共六十一頁，創(chuàng)作于2022年6月補圖定義7.9 設G為n階無向簡單圖，以V為頂點集，以所有為邊集使G成為完全圖Kn的添加邊組成的集合的圖，稱為G的補圖，記作G。若圖GG，則稱為G是自補圖。(1)為自補圖(2)和(3)互為補圖第五十張，PPT共六十一頁，創(chuàng)作于2022年6

24、月51在下圖中，(1)是(2)的補圖，當然(2)也是(1)的補圖，就是說，(1)，(2)互為補圖。同樣，(3)，(4)互為補圖。第五十一張，PPT共六十一頁，創(chuàng)作于2022年6月52圖的同構在圖論的研究中，我們更關心的是圖的結構, 而這種結構與頂點與邊的具體元素或與圖的圖形的畫法無關. 對此, 我們引進同構的概念.第五十二張，PPT共六十一頁，創(chuàng)作于2022年6月53圖同構(graph isomorphism)定義7.10 : 設兩個無向（有向）圖G1=,G2=, 若存在雙射f:V1V2, 滿足 uV1,vV1, e=(u,v)E1 e=(f(u),f(v)E2 (e=E1 e=E2 )并且e與e的重數相同， 則稱G1與G2同構, 記作G1G2說明: 同構的圖,其圖論性質完全一