離散數(shù)學(xué)圖論-圖的基本概念課件

1、圖 論圖的基本概念圖的基本概念七座橋所有的走法一共七座橋所有的走法一共有有7！=5040種。種。1736年，在經(jīng)過一年的研究之后，年，在經(jīng)過一年的研究之后，29歲的歐拉提交歲的歐拉提交了了哥尼斯堡七橋哥尼斯堡七橋的論文，圓滿解決了這一問題，的論文，圓滿解決了這一問題，同時(shí)開創(chuàng)了數(shù)學(xué)同時(shí)開創(chuàng)了數(shù)學(xué)新分支新分支-圖論圖論。圖圖 論論n在在許多應(yīng)用領(lǐng)域中許多應(yīng)用領(lǐng)域中：地圖導(dǎo)航、：地圖導(dǎo)航、網(wǎng)絡(luò)技術(shù)網(wǎng)絡(luò)技術(shù)研究及程序流程分析都會(huì)研究及程序流程分析都會(huì)遇到由遇到由“結(jié)點(diǎn)結(jié)點(diǎn)”和和“邊邊”組成的組成的圖圖n在在計(jì)算機(jī)許多學(xué)科中如：數(shù)據(jù)結(jié)構(gòu)、操作計(jì)算機(jī)許多學(xué)科中如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、網(wǎng)絡(luò)理論、信息的組織

2、與檢索均離系統(tǒng)、網(wǎng)絡(luò)理論、信息的組織與檢索均離不開由這種不開由這種“結(jié)點(diǎn)結(jié)點(diǎn)”和和“邊邊”組成的圖組成的圖以以及圖的特殊形式及圖的特殊形式-樹樹。n圖圖與樹是建立和處理離散對(duì)象及其與樹是建立和處理離散對(duì)象及其關(guān)系重關(guān)系重要要工具。工具。如地圖導(dǎo)航、如地圖導(dǎo)航、周游問題周游問題、圖像分、圖像分割等等割等等。一、圖的一、圖的概念概念1 1、無(wú)序積無(wú)序積定義：設(shè)定義：設(shè)A A，B B為任意的兩個(gè)集合，為任意的兩個(gè)集合， 稱稱 a a，b b aAbB aAbB 為為A A與與B B的無(wú)序積，記作的無(wú)序積，記作A & BA & B其元素其元素a a，b b 可簡(jiǎn)記為可簡(jiǎn)記為（a a，b

3、 b） 2 2、圖的定義、圖的定義 1 1）定義）定義1 1 一個(gè)一個(gè)無(wú)向圖無(wú)向圖是一個(gè)有序的二元組是一個(gè)有序的二元組 VE ，記作，記作G G，其中，其中 (1) (1) V V 稱為頂點(diǎn)集，其元素稱為稱為頂點(diǎn)集，其元素稱為頂點(diǎn)頂點(diǎn)或或結(jié)點(diǎn)結(jié)點(diǎn) (2) (2) E E稱為邊集稱為邊集，它是，它是無(wú)序積無(wú)序積V VV V的的多重子集多重子集，其元素稱為，其元素稱為無(wú)向邊無(wú)向邊， 簡(jiǎn)稱為簡(jiǎn)稱為邊邊 例：例：無(wú)向圖無(wú)向圖G = G = VE 其中其中 頂點(diǎn)集合頂點(diǎn)集合 V Vv1,v2,v3,v4 v1,v2,v3,v4 邊集合邊集合 E E(v1,v2),(v1,v2),(v2,v3),(v3,

4、v2),(v2,v3),(v3,v2),(v3,v1),(v3,v1),(v2,v2),(v2,v2),(v2,v2),(v2,v2),(v1,v2),(v1,v2), 園括號(hào)表示無(wú)向邊園括號(hào)表示無(wú)向邊 有平行邊有平行邊2 2） 定義定義2 2 一個(gè)一個(gè)有向圖有向圖是一個(gè)有序的二元組是一個(gè)有序的二元組VE，記作，記作D D，其中，其中 (1) V (1) V 稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn) (2)E(2)E為邊集，為邊集，它是笛卡兒積它是笛卡兒積 V VV V的有窮多重子集的有窮多重子集，其元素稱，其元素稱為為有向邊有向邊，簡(jiǎn)稱，簡(jiǎn)稱邊邊( (弧弧) )有向圖

5、有向圖D= D= 其中其中 V Vv1,v2,v3 v1,v2,v3 邊集合邊集合E E, v2,v1, , （與前面的關(guān)系的圖表示相當(dāng)）（與前面的關(guān)系的圖表示相當(dāng)）1 1）用）用G G表示無(wú)向圖，表示無(wú)向圖，D D表示有向圖。表示有向圖。 有時(shí)有時(shí)用用V(G)V(G)，E(G)E(G)分別表示分別表示G G的頂點(diǎn)集和邊集。的頂點(diǎn)集和邊集。2 2）用）用|V(G)|V(G)|，|E(G)|E(G)|分別表示分別表示G G的頂點(diǎn)數(shù)和邊的頂點(diǎn)數(shù)和邊數(shù)數(shù) 若若V(G)V(G)n n，則稱，則稱G G為為n n階圖階圖。對(duì)。對(duì)有向圖有相同定義。有向圖有相同定義。3 3）在圖）在圖G G中，若中，若邊集

6、邊集E(G)E(G)，則稱，則稱G G為為零圖零圖 若若G G為為n n階圖，則稱階圖，則稱G G為為n n階零圖階零圖，記作，記作N Nn n，特別是稱，特別是稱N N1 1為為平凡圖平凡圖4 4）在用圖形表示一個(gè)圖時(shí)，若給每個(gè)結(jié)點(diǎn)和每一條邊均指定一個(gè)）在用圖形表示一個(gè)圖時(shí)，若給每個(gè)結(jié)點(diǎn)和每一條邊均指定一個(gè)符號(hào)（字母或數(shù)字），則稱這樣的圖為符號(hào)（字母或數(shù)字），則稱這樣的圖為標(biāo)定標(biāo)定圖。圖。5) 5) 常用常用e ek k表示邊表示邊(v(vi i，v vj j)( )( 或或 ) ) 設(shè)設(shè)G GV E 為無(wú)向圖，為無(wú)向圖，e ek k = (v = (vi i，v vj j)E)E， 則則稱

7、稱v vi i，v vj j為為e ek k的端點(diǎn)的端點(diǎn)， e ek k與與v vi i、v vj j是彼此是彼此相關(guān)聯(lián)的相關(guān)聯(lián)的 起、終點(diǎn)起、終點(diǎn)相同的邊稱為相同的邊稱為環(huán)環(huán) 不不與任何邊關(guān)聯(lián)的結(jié)點(diǎn)稱為與任何邊關(guān)聯(lián)的結(jié)點(diǎn)稱為孤立點(diǎn)孤立點(diǎn)（包括有向圖（包括有向圖) )6 6）鄰接：）鄰接： 邊的相鄰邊的相鄰：e ek k，e el lEE若若e ek k與與e el l至少有一個(gè)公共端點(diǎn)，至少有一個(gè)公共端點(diǎn)， 則稱則稱e ek k與與e el l是相鄰的是相鄰的 頂點(diǎn)的相鄰頂點(diǎn)的相鄰：若：若e et tEE，使得，使得e et t = v = ， 則稱則稱v vi i為為e et t的始點(diǎn)，的

8、始點(diǎn)，v vj j為為e et t的終點(diǎn)，的終點(diǎn)， 并稱并稱v vi i鄰接到鄰接到v vj j，v vj j鄰接于鄰接于v vi i 兩個(gè)結(jié)點(diǎn)為一條邊的端點(diǎn)，則稱兩個(gè)結(jié)點(diǎn)兩個(gè)結(jié)點(diǎn)為一條邊的端點(diǎn)，則稱兩個(gè)結(jié)點(diǎn)互為鄰接點(diǎn)互為鄰接點(diǎn)， 也稱也稱邊關(guān)聯(lián)于這兩個(gè)結(jié)點(diǎn)邊關(guān)聯(lián)于這兩個(gè)結(jié)點(diǎn)，或稱兩個(gè)結(jié)點(diǎn)鄰接于此邊，或稱兩個(gè)結(jié)點(diǎn)鄰接于此邊。7）平行邊：）平行邊： 在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1 1條，則稱這些條，則稱這些邊為邊為平行邊平行邊，平行邊的條數(shù)稱為，平行邊的條數(shù)稱為重?cái)?shù)重?cái)?shù) 在在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如

9、果多于1 1條，條，并且它們并且它們的的方向方向相同相同，則稱這些邊為則稱這些邊為平行邊平行邊8 8）多重圖和簡(jiǎn)單圖：）多重圖和簡(jiǎn)單圖：含平行邊的圖稱為多重圖含平行邊的圖稱為多重圖既既不含平行邊也不含環(huán)的圖稱為不含平行邊也不含環(huán)的圖稱為（主要討論簡(jiǎn)單圖（主要討論簡(jiǎn)單圖） 4 4、結(jié)點(diǎn)的度、結(jié)點(diǎn)的度 1 1) ) 定義定義4 4 設(shè)設(shè)G GVE為無(wú)向圖，為無(wú)向圖， v Vv V，稱，稱v v作為邊的端點(diǎn)作為邊的端點(diǎn)的次數(shù)之和的次數(shù)之和為為v v的的度數(shù)度數(shù)，簡(jiǎn)稱為，簡(jiǎn)稱為度度，記作，記作d dG G(v)(v)，簡(jiǎn)記為簡(jiǎn)記為d(v)d(v)，即為：結(jié)點(diǎn)即為：結(jié)點(diǎn)v v 所關(guān)聯(lián)的邊的總條數(shù)所關(guān)聯(lián)的

10、邊的總條數(shù) 關(guān)于有向圖關(guān)于有向圖D DV E 有：有： vVvV，稱，稱v v作為邊的作為邊的始點(diǎn)的次數(shù)之和始點(diǎn)的次數(shù)之和為為v v的的出度出度，記作，記作d d+ +(v)(v)，稱稱v v作為邊的作為邊的終點(diǎn)終點(diǎn)的次數(shù)之和為的次數(shù)之和為v v的的入度入度，記作，記作d d- -(v)(v) 稱稱d d+ +(v)+ d(v)+ d- -(v)(v)為為 v v的度數(shù)，記作的度數(shù)，記作d dD D(v).(v). 2) 2) 稱度數(shù)為稱度數(shù)為1 1的頂點(diǎn)為的頂點(diǎn)為懸掛頂點(diǎn)懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為，與它關(guān)聯(lián)的邊稱為懸掛邊懸掛邊 根據(jù)結(jié)點(diǎn)的度數(shù)可將結(jié)點(diǎn)分為：根據(jù)結(jié)點(diǎn)的度數(shù)可將結(jié)點(diǎn)分為： 度為偶

11、數(shù)度為偶數(shù)( (奇數(shù)奇數(shù)) )的頂點(diǎn)稱為的頂點(diǎn)稱為偶度偶度頂點(diǎn)頂點(diǎn)( (奇度頂點(diǎn)奇度頂點(diǎn)).). 一個(gè)環(huán)提供的度為一個(gè)環(huán)提供的度為2 2（有向圖的環(huán)提供入度（有向圖的環(huán)提供入度1 1和出度和出度1 1） 3 3）定義：）定義： (G) = maxd(v)|vV(G) (G) = maxd(v)|vV(G) 為圖為圖G G中結(jié)點(diǎn)最大的度中結(jié)點(diǎn)最大的度 (G) = mind(v)|vV(G) (G) = mind(v)|vV(G) 為圖為圖G G中結(jié)點(diǎn)最小的度中結(jié)點(diǎn)最小的度 簡(jiǎn)記為簡(jiǎn)記為 、定義：定義： (D) = maxd(D) = maxd(v)|vV(D) (v)|vV(D) 為圖為圖D D

12、中結(jié)點(diǎn)最大中結(jié)點(diǎn)最大的的入入度度 (D) = maxd(D) = maxd(v)|vV(D) (v)|vV(D) 為圖為圖D D中結(jié)點(diǎn)最大的中結(jié)點(diǎn)最大的出出度度 - -(D) = mind(D) = mind(v)|vV(D) (v)|vV(D) 為圖為圖D D中結(jié)點(diǎn)最小中結(jié)點(diǎn)最小的的入入度度 (D) = mind(D) = mind(v)|vV(D) (v)|vV(D) 為圖為圖D D中結(jié)點(diǎn)最小的中結(jié)點(diǎn)最小的出出度度5 5、握手定理（歐拉）、握手定理（歐拉）1)1)定理定理1 1 設(shè)設(shè)G G為任意無(wú)向圖為任意無(wú)向圖,V,Vvv1 1，v v2 2，v vn n,E E = m= m， 則則

13、d(vd(vi i) ) 2m2m ( (所有結(jié)點(diǎn)的度數(shù)值和為邊數(shù)的所有結(jié)點(diǎn)的度數(shù)值和為邊數(shù)的2 2倍倍) ) 證證: G: G中每條邊中每條邊( (包括環(huán)包括環(huán)) )均有兩個(gè)端點(diǎn)，所以在計(jì)算均有兩個(gè)端點(diǎn)，所以在計(jì)算G G中各頂點(diǎn)度數(shù)之和中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供時(shí)，每條邊均提供2 2度，當(dāng)然，度，當(dāng)然，m m條邊共提供條邊共提供2m2m度度2) 2) 定理定理2 2 設(shè)設(shè)D D為任意有向圖為任意有向圖,V,Vvv1 1，v v2 2，v vn n,|E| = m ,|E| = m ， 則則 d d+ +(v(vi i) =) = d d- -(v(vi i) = m) = m 且且d(

14、vd(vi i) )2m2m3) 3) 推論推論 任何圖任何圖( (無(wú)向的或有向的無(wú)向的或有向的) )中，中，奇度頂點(diǎn)奇度頂點(diǎn)的的個(gè)數(shù)個(gè)數(shù)是是偶數(shù)個(gè)偶數(shù)個(gè)4) 4) 結(jié)點(diǎn)的度數(shù)序列結(jié)點(diǎn)的度數(shù)序列 (1) (1) 設(shè)設(shè)G GVE為一個(gè)為一個(gè)n n階無(wú)向圖，階無(wú)向圖，V Vvv1 1，v v2 2，v vn n 稱稱d(vd(v1 1) )，d(vd(v2 2) )， ，d(vd(vn n) ) 為為G G的的度數(shù)列度數(shù)列 注：由推論可知，不是任何一個(gè)非負(fù)整數(shù)序列均可作為一個(gè)圖的度數(shù)列。注：由推論可知，不是任何一個(gè)非負(fù)整數(shù)序列均可作為一個(gè)圖的度數(shù)列。 條件：條件：奇度數(shù)奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)應(yīng)該是的結(jié)點(diǎn)

15、個(gè)數(shù)應(yīng)該是偶數(shù)個(gè)偶數(shù)個(gè) （2 2）序列的可圖化）序列的可圖化：對(duì)一個(gè)整數(shù)：對(duì)一個(gè)整數(shù)序列序列d=(dd=(d1 1,d,d2 2, ,d dn n),),若存在以若存在以n n個(gè)頂點(diǎn)的個(gè)頂點(diǎn)的n n階階無(wú)向圖無(wú)向圖G G，有，有d(vd(vi i)=d)=di i ，稱該序列是，稱該序列是可圖化的。可圖化的。 特別的，如果得到的是簡(jiǎn)單圖，稱該序列是特別的，如果得到的是簡(jiǎn)單圖，稱該序列是可簡(jiǎn)單圖化的?？珊?jiǎn)單圖化的。 （3 3）定理）定理 設(shè)非負(fù)整數(shù)列設(shè)非負(fù)整數(shù)列d d(d1(d1，d2d2，dn)dn)，則，則d d是可圖化的是可圖化的當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) d di i 是偶數(shù)是偶數(shù)( (序列之和必

16、須是偶數(shù)序列之和必須是偶數(shù)) ) （4 4）由于簡(jiǎn)單圖中沒有平行邊及環(huán)）由于簡(jiǎn)單圖中沒有平行邊及環(huán) 定理：設(shè)定理：設(shè)G G為任意為任意n n階無(wú)向階無(wú)向簡(jiǎn)單圖簡(jiǎn)單圖，則，則 (G(G)= n-1)dd2 2ddn n=1 =1 且且d di i= = 偶數(shù)偶數(shù) d4=d4=（3,3,3,13,3,3,1） 分析分析 d5= d5=（4,4,3,3,2,24,4,3,3,2,2）二、圖的同構(gòu)二、圖的同構(gòu)定義：設(shè)定義：設(shè)G1G1VlE1，G2=V2G2=E2為兩個(gè)無(wú)向圖為兩個(gè)無(wú)向圖( (有向圖有向圖) )， 若存在雙射函數(shù)若存在雙射函數(shù) f f：V1 V2 V1 V2 對(duì)于對(duì)于 vivi，vjvj

17、 V1V1，(vi(vi，vj) vj) E1 E1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)(f(vi)(f(vi), ,f(vj)f(vj) E2 E2 并且并且(vi(vi，vj) vj) 與與(f(vi),f(vj(f(vi),f(vj)的重?cái)?shù)的重?cái)?shù)相同，則稱相同，則稱G1G1與與G2G2是是同構(gòu)同構(gòu)的，記作的，記作Gl Gl G2 G2。 對(duì)有向圖有相同的定義。對(duì)有向圖有相同的定義。 定義說明了定義說明了: :兩個(gè)圖的各結(jié)點(diǎn)之間，如果存在著一一對(duì)應(yīng)關(guān)系兩個(gè)圖的各結(jié)點(diǎn)之間，如果存在著一一對(duì)應(yīng)關(guān)系 f 這種對(duì)應(yīng)關(guān)系又保持了這種對(duì)應(yīng)關(guān)系又保持了結(jié)點(diǎn)間的鄰接關(guān)系結(jié)點(diǎn)間的鄰接關(guān)系，那么這兩個(gè)圖就是同構(gòu)的那么這兩個(gè)圖就

18、是同構(gòu)的 在有向圖的情況下，在有向圖的情況下， f 不但應(yīng)該保持結(jié)點(diǎn)間的鄰接關(guān)系，還應(yīng)不但應(yīng)該保持結(jié)點(diǎn)間的鄰接關(guān)系，還應(yīng)該該保持邊的方向。保持邊的方向。結(jié)點(diǎn)數(shù)相同邊數(shù)相同結(jié)點(diǎn)數(shù)相同邊數(shù)相同結(jié)點(diǎn)的度相同結(jié)點(diǎn)的度相同但是兩個(gè)圖但是兩個(gè)圖不同構(gòu)不同構(gòu)注注：1 1) ) 兩個(gè)圖同構(gòu)的必要條件兩個(gè)圖同構(gòu)的必要條件階數(shù)相同階數(shù)相同（頂點(diǎn)）（頂點(diǎn)）邊數(shù)相同邊數(shù)相同度數(shù)相同的頂點(diǎn)數(shù)相同度數(shù)相同的頂點(diǎn)數(shù)相同同構(gòu)同構(gòu)的的必要條件，并不是充分條件必要條件，并不是充分條件2 2) )圖之間的圖之間的同構(gòu)關(guān)系同構(gòu)關(guān)系可看成全體圖集合上的二元可看成全體圖集合上的二元關(guān)系。關(guān)系。 具有具有自反性，對(duì)稱性和傳遞性，自反性，對(duì)

19、稱性和傳遞性，是是等價(jià)關(guān)系。等價(jià)關(guān)系。 同構(gòu)同構(gòu)的圖為一個(gè)等價(jià)類，在的圖為一個(gè)等價(jià)類，在同構(gòu)的意義之下都可以看同構(gòu)的意義之下都可以看成是一個(gè)圖。成是一個(gè)圖。例例 (1)(1)畫出畫出4 4階階3 3條邊的所有非同構(gòu)的條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖無(wú)向簡(jiǎn)單圖 結(jié)點(diǎn)個(gè)數(shù)結(jié)點(diǎn)個(gè)數(shù)與與邊數(shù)相同邊數(shù)相同，只需找出，只需找出頂點(diǎn)度數(shù)序列不同頂點(diǎn)度數(shù)序列不同的圖（的圖（2 2 3 36 6）如何將度數(shù)如何將度數(shù)6 6分配給分配給4 4個(gè)結(jié)點(diǎn)：個(gè)結(jié)點(diǎn)： 1 1 1 3 1 1 1 3 相應(yīng)的圖相應(yīng)的圖 2 2 1 1 2 2 1 1 2 2 2 0 2 2 2 0例例 (2)(2)畫出畫出3 3階階2 2條邊的

20、所有非同構(gòu)的條邊的所有非同構(gòu)的有向簡(jiǎn)單圖有向簡(jiǎn)單圖 結(jié)點(diǎn)個(gè)數(shù)與邊數(shù)相同，只需找出結(jié)點(diǎn)個(gè)數(shù)與邊數(shù)相同，只需找出頂點(diǎn)度（出度及入度）數(shù)序列不同頂點(diǎn)度（出度及入度）數(shù)序列不同的圖的圖 結(jié)點(diǎn)總度數(shù)：結(jié)點(diǎn)總度數(shù)： 2 22 24 4 度數(shù)分配度數(shù)分配 1 2 1 1 2 1 按出度與入度分配：按出度與入度分配：入度列入度列 1 1 01 1 0出度列出度列 0 1 0 1 1 1入度列入度列 0 2 00 2 0出度列出度列 1 0 1 0 1 1入度列入度列 1 0 11 0 1出度列出度列 0 2 00 2 0度數(shù)分配度數(shù)分配 2 2 0 2 2 0 按出度與入度分配：按出度與入度分配：入度列入度列

21、 1 1 01 1 0出度列出度列 1 1 01 1 0這只是對(duì)較為簡(jiǎn)單的情這只是對(duì)較為簡(jiǎn)單的情況給出的非同構(gòu)圖，對(duì)況給出的非同構(gòu)圖，對(duì)于一般的情況（于一般的情況（n,m)n,m)圖圖到目前為止還沒有解決到目前為止還沒有解決 1 1) )完全圖完全圖 定義定義 設(shè)設(shè)G G為為n n階無(wú)向階無(wú)向簡(jiǎn)單圖簡(jiǎn)單圖，若，若G G中每個(gè)頂點(diǎn)均與其余的中每個(gè)頂點(diǎn)均與其余的n n1 1個(gè)頂點(diǎn)相鄰，個(gè)頂點(diǎn)相鄰，則稱則稱G G為為n n階無(wú)向完全圖，簡(jiǎn)稱階無(wú)向完全圖，簡(jiǎn)稱n n階完全圖階完全圖，記作，記作KnKn(n1)(n1) 設(shè)設(shè)D D為為n n階有向簡(jiǎn)單圖，若階有向簡(jiǎn)單圖，若D D中每個(gè)頂點(diǎn)都中每個(gè)頂點(diǎn)都鄰接到鄰接到其余的其余的n n1 1個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，又又鄰接于鄰接于其余的其余的 n n1 1個(gè)頂點(diǎn)，則稱個(gè)頂點(diǎn)，則稱D D是是 n n 階階有向完全圖有向完全圖 可畫圖表示（無(wú)向圖可畫圖表示（無(wú)向圖5 5階、有向圖階、有向圖3 3階和階和4 4階）階） 2)2)完全圖的性質(zhì)：完全圖的性質(zhì)： n n階無(wú)向完全圖階無(wú)向完全圖G G的邊數(shù)與結(jié)點(diǎn)的關(guān)系的邊數(shù)與結(jié)點(diǎn)的關(guān)系 m = m = n (n-1)/2n (n-1)/2