第七章 第一講 無向圖及有向圖

第七章第一講無向圖及有向圖第一頁，共三十四頁，編輯于2023年，星期四第二頁，共三十四頁，編輯于2023年，星期四第一講無向圖及有向圖知識結(jié)構(gòu)圖的定義圖的一些概念和規(guī)定簡單圖和多重圖頂點的度數(shù)與握手定理圖的同構(gòu)子圖與補圖第三頁，共三十四頁，編輯于2023年，星期四

引例1：哥尼斯堡七橋問題（圖論應用的開始）問：能否從某地出發(fā)，通過每橋恰好一次，走遍了七橋

后又返回到原處？瑞士數(shù)學家歐拉在1736年發(fā)表了一篇論文討論這個問題，指出這個問題無解。普雷格爾河第四頁，共三十四頁，編輯于2023年，星期四歐拉：傳奇的一生年少時，聽從父親的安排，巴塞爾大學，學習神學和希伯來語，結(jié)果被約翰·伯努利欣賞，17歲獲得碩士學位之后，才開始專供數(shù)學。為獲得圣彼得堡科學院的醫(yī)學部的職位空缺，歐拉在巴塞爾便全力投入生理學的研究，并出席醫(yī)學報告會。1727年，等他到達俄羅斯時，葉卡捷琳娜一世女皇去世，他進入數(shù)學部。1733年，歐拉回到瑞士，并結(jié)婚，一生共生育13個孩子，5個存活。為了贏得巴黎獎金而投身于一個天文學問題，那是幾個有影響的大數(shù)學家搞了幾個月時間的，歐拉在三天之后把它解決了?？墒沁^分的勞累使他得了一場病，病中右眼失明了。歐拉到底出了多少著作，直至1936年人們也沒有確切的了解。但據(jù)估計，要出版已經(jīng)搜集到的歐拉著作，將需用大4開本60至80卷。彼得堡學院為了整理他的著作整整花了47年。第五頁，共三十四頁，編輯于2023年，星期四問題2(哈密頓環(huán)球旅行問題，1857年):

十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？哈密頓圈（環(huán)球旅行游戲）第六頁，共三十四頁，編輯于2023年，星期四問題3(四色問題):

對任何一張地圖進行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了.問題4(關鍵路徑問題):

一項工程任務,大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機,都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個工序才能開始.即它們之間存在完成的先后次序關系,一般認為這些關系是預知的,而且也能夠預計完成每個工序所需要的時間.

這時工程領導人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進度的要害工序是哪幾個？第七頁，共三十四頁，編輯于2023年，星期四二、圖的概念

設A，B為任意的兩個集合，{{a,b}|a∈A∧b∈B}為A與B的無序積，記作A&B?？蓪o序積中的無序?qū)a,b}記為(a,b)，并且允許a＝b。無論a,b是否相等，均有(a,b)＝(b,a)，故A&B＝B&A。元素可以重復出現(xiàn)的集合稱為多重集合或者多重集。例如

多重集合{a,a,b,b,b,c,d},{(a,a),(b,b),(b,b)}.

第八頁，共三十四頁，編輯于2023年，星期四定義1一個無向圖（undirectedgraph）是一個有序的二元組<V，E>,記作G，其中 （1）V≠稱為頂點集，其元素稱為頂點或結(jié)點（vertices,nodes）。 （2）E稱為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊（edges）。例1(1)給定無向圖G＝<V,E>，其中V＝{v1,v2,v3,v4,v5}，

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.第九頁，共三十四頁，編輯于2023年，星期四例1（2）E＝{<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,<d,c>,<c,b>}

定義2一個有向圖（directedgraph）是一個有序的二元組<V，E>，記作D，其中（1）V≠稱為頂點集，其元素稱為頂點或結(jié)點。（2）E為邊集，它是笛卡兒積V×V的多重子集，其元素稱為有向邊，簡稱邊。第十頁，共三十四頁，編輯于2023年，星期四圖的一些概念和規(guī)定G表示無向圖，但有時用G泛指圖(無向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點集和邊集。若|V(G)|＝n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。若邊集E(G)＝，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖(trivialgraph)。

第十一頁，共三十四頁，編輯于2023年，星期四關聯(lián)與關聯(lián)次數(shù)、環(huán)、孤立點設G＝<V,E>為無向圖，ek＝(vi,vj)∈E， 稱vi,vj為ek的端點，ek與vi或ek與vj是彼此相關聯(lián)的。 若vi≠vj，則稱ek與vi或ek與vj的關聯(lián)次數(shù)為1。 若vi＝vj，則稱ek與vi的關聯(lián)次數(shù)為2，并稱ek為環(huán)。 任意的vl∈V，若vl≠vi且vl≠vj，則稱ek與vl的關聯(lián)次數(shù)為0。設D＝<V,E>為有向圖，ek＝<vi,vj>∈E，稱vi,vj為ek的端點。 若vi＝vj，則稱ek為D中的環(huán)。無論在無向圖中還是在有向圖中，無邊關聯(lián)的頂點均稱為孤立點(isolatedvertices)。

第十二頁，共三十四頁，編輯于2023年，星期四相鄰與鄰接設無向圖G＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝(vi，vj)，則稱vi與vj是相鄰的。 若ek與el至少有一個公共端點，則稱ek與el是相鄰的。設有向圖D＝<V，E>，vi，vj∈V，ek，el∈E。 若et∈E，使得et＝<vi，vj>，則稱vi為et的始點，vj為et的終點，并稱vi鄰接到vj，vj鄰接于vi。 若ek的終點為el的始點，則稱ek與el相鄰(adjacent)。vivjekelvivjekel第十三頁，共三十四頁，編輯于2023年，星期四簡單圖與多重圖定義3在無向圖中，關聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。 在有向圖中，關聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊(paralleledges)。含平行邊的圖稱為多重圖(multigraph)。 既不含平行邊也不含環(huán)的圖稱為簡單圖(simplegraph)。例如：在圖 中e5與e6是平行邊， 不是簡單圖。第十四頁，共三十四頁，編輯于2023年，星期四頂點的度數(shù)(degree)定義4設G＝<V,E>為一無向圖，v∈V，稱v作為邊的端點次數(shù)之和為v的度數(shù)，簡稱為度，記做dG(v)。 在不發(fā)生混淆時，簡記為d(v)。

設D＝<V，E>為有向圖，v∈V， 稱v作為邊的始點次數(shù)之和為v的出度(out-degree)，記做d+D(v)，簡記作d+(v)。 稱v作為邊的終點次數(shù)之和為v的入度(in-degree)，記做d-D(v)，簡記作d-(v)。 稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。第十五頁，共三十四頁，編輯于2023年，星期四設G＝<V,E>為一個n階無向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對于頂點標定的無向圖，它的度數(shù)列是唯一的。類似地，設D＝<V,E>為一個n階有向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，…，d+(vn)與d-(v1)，d-(v2)，…，d-(vn)分別為D的出度列和入度列。度數(shù)列為

4,4,2,1,3。度數(shù)列，出度列，入度列分別為5,3,3,34,0,2,11,3,1,2第十六頁，共三十四頁，編輯于2023年，星期四圖的度數(shù)的相關概念在無向圖G中，

最大度 △(G)＝max{d(v)|v∈V(G)}

最小度

δ(G)＝min{d(v)|v∈V(G)}在有向圖D中，

最大出度 △+(D)＝max{d+(v)|v∈V(D)}

最小出度

δ+(D)＝min{d+(v)|v∈V(D)}

最大入度

△-(D)＝max{d-(v)|v∈V(D)}

最小入度

δ-(D)＝min{d-(v)|v∈V(D)}稱度數(shù)為1的頂點為懸掛頂點，與它關聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點稱為偶度(奇度)頂點。

第十七頁，共三十四頁，編輯于2023年，星期四圖的度數(shù)舉例d(v1)＝4(注意，環(huán)提供2度)，△＝4，δ＝1，v4是懸掛頂點，e7是懸掛邊。d+(a)＝4，d-(a)＝1

△+＝4δ+＝0△-＝3δ-＝1度數(shù)列：4、4、2、1、3出：4、0、2、1入：1、3、1、2邊：7度數(shù)列：5、3、3、3邊數(shù)：7第十八頁，共三十四頁，編輯于2023年，星期四握手定理(TheHandshakingTheorem)定理1設G＝<V,E>為任意無向圖，V＝{v1,v2,…,vn}， |E|＝m，則說明 任何無向圖中，各頂點度數(shù)之和等于邊數(shù)的兩倍。證明 G中每條邊(包括環(huán))均有兩個端點，所以在計算G中各頂點度數(shù)之和時， 每條邊均提供2度，當然，m條邊，共提供2m度。

定理2設D＝<V,E>為任意有向圖，V＝{v1,v2,…,vn}， |E|＝m，則第十九頁，共三十四頁，編輯于2023年，星期四推論推論 任何圖(無向或有向)中，奇度頂點的個數(shù)是偶數(shù)。證明 設G＝<V，E>為任意一圖，令

V1＝{v|v∈V∧d(v)為奇數(shù)}

V2＝{v|v∈V∧d(v)為偶數(shù)} 則V1∪V2＝V，V1∩V2＝，由握手定理可知

由于2m和，所以為偶數(shù)，但因V1中頂點度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)。第二十頁，共三十四頁，編輯于2023年，星期四例：(3,3,2,1)，(3,2,2,1,1)(3,3,2,2)、(3,2,2,2,1)是否可圖化？

解：

(3,3,2,1)，(3,2,2,1,1)不可以圖化

(3,3,2,2)可以圖化

(3,2,2,2,1)可以圖化

若非負整數(shù)列可以對應為圖的度數(shù)列，則稱之為可圖化。第二十一頁，共三十四頁，編輯于2023年，星期四定理4設G為任意n階無向簡單圖，則△(G)≤n-1。證明 因為G既無平行邊也無環(huán)， 所以G中任何頂點v至多與其余的n-1個頂點均相鄰， 于是d(v)≤n-1，由于v的任意性，所以△(G)≤n-1。例2判斷下列各非負整數(shù)列哪些可圖化的？哪些可簡單圖化的？

(1)(5,5,4,4,2,1) 不可圖化。(2)(5,4,3,2,2)

可圖化，不可簡單圖化。若它可簡單圖化，設所得圖為G，則(G)＝max{5,4,3,2,2}＝5，這與定理矛盾第二十二頁，共三十四頁，編輯于2023年，星期四(3)(3,3,3,1)

可圖化，不可簡單圖化。假設可以簡單圖化，設G＝<V，E>以該序列為度數(shù)列設V＝{v1,v2,v3,v4}且d(v1)＝d(v2)＝d(v3)＝3,d(v4)＝1， 由于d(v4)＝1，因而v4只能與v1，v2，v3之一相鄰，去掉v4后，與v4關聯(lián)的邊也去掉，于是剩余的v1，v2，v3組成的圖的度數(shù)應該是2、3、3，此時因為最大度為3，不滿足≤n-1=2的要求，因此這三個點構(gòu)成的圖必定有平行邊或者環(huán)，不是簡單圖，此時若加入v4及與v4關聯(lián)的邊構(gòu)成的圖必定也不是簡單圖。即有(3)中序列也不可簡單圖化。

第二十三頁，共三十四頁，編輯于2023年，星期四(5)(4,4,3,3,2,2)

可簡單圖化。下圖中兩個6階無向簡單圖都以(5)中序列為度數(shù)列。第二十四頁，共三十四頁，編輯于2023年，星期四定義5設G1＝<V1,E1>，G2＝<V2,E2>為兩個無向圖， 若存在雙射函數(shù)f：V1→V2，對于vi,vj∈V1，(vi,vj)∈E1當且僅當 (f(vi),f(vj))∈E2， 并且(vi,vj)與(f(vi),f(vj))的重數(shù)相同， 則稱G1與G2是同構(gòu)的(isomorphic)，記做G1≌G2。說明 (1)點數(shù)、邊數(shù)和度數(shù)列對影響等。 (2)在圖同構(gòu)的意義下，圖的數(shù)學定義與圖形表示是一一對應的。

方法一：邊伸縮方法二：點挪動abcdabcd第二十五頁，共三十四頁，編輯于2023年，星期四≌≌×≌abedceadcbe1e1e2e2第二十六頁，共三十四頁，編輯于2023年，星期四完全圖(completegraph)定義6設G為n階無向簡單圖，若G中每個頂點均與其余的n-1個頂點相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記做Kn(n≥1)。 設D為n階有向簡單圖，若D中任意兩個不同的頂點之間都存在兩條方向相反的邊，則稱D是n階有向完全圖。n階無向完全圖的邊數(shù)為： n(n-1)/2n階有向完全圖的邊數(shù)為： n(n-1)第二十七頁，共三十四頁，編輯于2023年，星期四完全圖舉例K53階有向完全圖4階競賽圖第二十八頁，共三十四頁，編輯于2023年，星期四子圖(subgraph)定義8設G＝<V,E>，G＝<V,E>為兩個圖(同為無向圖或同為有向圖)，若VV且EE，則稱G是G的子圖，G為G的母圖，記作GG。 若VV或EE，則稱G為G的真子圖。 若V＝V，則稱G為G的生成子圖。 設G＝<V,E>為一圖，V1V且V1≠，稱以V1為頂點集，以G中兩個端點都在V1中的邊組成邊集E1的圖為G的V1導出的子圖（inducedsubgraph），

記作G[V1]。 設E1E且E1≠，稱以E1為邊集，以E1中邊關聯(lián)的頂點為頂點集V1的圖為G的E1導出的子圖（