第七章 第一講 無(wú)向圖及有向圖

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

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

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

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

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

一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺(tái)機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個(gè)工序才能開(kāi)始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間.

這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？第七頁(yè)，共三十四頁(yè)，編輯于2023年，星期四二、圖的概念

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

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

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

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

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

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

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

設(shè)D＝<V，E>為有向圖，v∈V， 稱v作為邊的始點(diǎn)次數(shù)之和為v的出度(out-degree)，記做d+D(v)，簡(jiǎn)記作d+(v)。 稱v作為邊的終點(diǎn)次數(shù)之和為v的入度(in-degree)，記做d-D(v)，簡(jiǎn)記作d-(v)。 稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。第十五頁(yè)，共三十四頁(yè)，編輯于2023年，星期四設(shè)G＝<V,E>為一個(gè)n階無(wú)向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。類似地，設(shè)D＝<V,E>為一個(gè)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第十六頁(yè)，共三十四頁(yè)，編輯于2023年，星期四圖的度數(shù)的相關(guān)概念在無(wú)向圖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的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點(diǎn)稱為偶度(奇度)頂點(diǎn)。

第十七頁(yè)，共三十四頁(yè)，編輯于2023年，星期四圖的度數(shù)舉例d(v1)＝4(注意，環(huán)提供2度)，△＝4，δ＝1，v4是懸掛頂點(diǎn)，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第十八頁(yè)，共三十四頁(yè)，編輯于2023年，星期四握手定理(TheHandshakingTheorem)定理1設(shè)G＝<V,E>為任意無(wú)向圖，V＝{v1,v2,…,vn}， |E|＝m，則說(shuō)明 任何無(wú)向圖中，各頂點(diǎn)度數(shù)之和等于邊數(shù)的兩倍。證明 G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)， 每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。

定理2設(shè)D＝<V,E>為任意有向圖，V＝{v1,v2,…,vn}， |E|＝m，則第十九頁(yè)，共三十四頁(yè)，編輯于2023年，星期四推論推論 任何圖(無(wú)向或有向)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(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中頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)。第二十頁(yè)，共三十四頁(yè)，編輯于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)可以圖化

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

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

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

可圖化，不可簡(jiǎn)單圖化。假設(shè)可以簡(jiǎn)單圖化，設(shè)G＝<V，E>以該序列為度數(shù)列設(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關(guān)聯(lián)的邊也去掉，于是剩余的v1，v2，v3組成的圖的度數(shù)應(yīng)該是2、3、3，此時(shí)因?yàn)樽畲蠖葹?，不滿足≤n-1=2的要求，因此這三個(gè)點(diǎn)構(gòu)成的圖必定有平行邊或者環(huán)，不是簡(jiǎn)單圖，此時(shí)若加入v4及與v4關(guān)聯(lián)的邊構(gòu)成的圖必定也不是簡(jiǎn)單圖。即有(3)中序列也不可簡(jiǎn)單圖化。

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

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

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

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