《無向圖及有向》PPT課件

《《無向圖及有向》PPT課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第一講無向圖及有向圖知識結(jié)構(gòu)圖的定義圖的一些概念和規(guī)定簡單圖和多重圖頂點(diǎn)的度數(shù)與握手定理圖的同構(gòu)子圖與補(bǔ)圖引例1：哥尼斯堡七橋問題（圖論應(yīng)用的開始）問：能否從某地出發(fā)，通過每橋恰好一次，走遍了七橋后又返回到原處？瑞士數(shù)學(xué)家歐拉在1736年發(fā)表了一篇論文討論這個(gè)問題，指出這個(gè)問題無解。普雷格爾河歐拉：傳奇的一生年少時(shí)，聽從父親的安排，巴塞爾大學(xué)，學(xué)習(xí)神學(xué)和希伯來語，結(jié)果被約翰·伯努利欣賞，17歲獲得碩士學(xué)位之后，才開始專供數(shù)學(xué)。為獲得圣彼得堡科學(xué)院的醫(yī)學(xué)部的職位空缺，歐拉在巴塞爾便全力投入生理學(xué)的研究，并出席醫(yī)學(xué)報(bào)告會。1727年，等他到達(dá)俄羅斯時(shí)，葉卡捷琳娜一世女皇去世，他進(jìn)入數(shù)學(xué)部。17

2、33年，歐拉回到瑞士，并結(jié)婚，一生共生育13個(gè)孩子，5個(gè)存活。為了贏得巴黎獎(jiǎng)金而投身于一個(gè)天文學(xué)問題，那是幾個(gè)有影響的大數(shù)學(xué)家搞了幾個(gè)月時(shí)間的，歐拉在三天之后把它解決了?？墒沁^分的勞累使他得了一場病，病中右眼失明了。歐拉到底出了多少著作，直至1936年人們也沒有確切的了解。但據(jù)估計(jì)，要出版已經(jīng)搜集到的歐拉著作，將需用大4開本60至80卷。彼得堡學(xué)院為了整理他的著作整整花了47年。問題2(哈密頓環(huán)球旅行問題，1857年):十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？哈密頓圈（環(huán)球旅行游戲）問題3(四色問題):對任何一張地圖進(jìn)

3、行著色，兩個(gè)共同邊界的國家染不同的顏色，則只需要四種顏色就夠了.問題4(關(guān)鍵路徑問題):一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個(gè)工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間.這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？二、圖的概念設(shè)A，B為任意的兩個(gè)集合，{{a,b}

4、a∈A∧b∈B}為A與B的無序積，記作A&B。可將無序積中的無序?qū)a,b}記為(a,b)，并且允許a

5、＝b。無論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)}.定義1一個(gè)無向圖（undirectedgraph）是一個(gè)有序的二元組,記作G，其中（1）V≠?稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)（vertices,nodes）。（2）E稱為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊（edges）。例1(1)給定無向圖G＝，其中V＝{v1,v2,v3,v4,v5}，E={(v1,v1),(v1,v2),(v2,v3),(v2

6、,v3),(v2,v5),(v1,v5),(v4,v5)}.例1（2）E＝{,,,,,,}定義2一個(gè)有向圖（directedgraph）是一個(gè)有序的二元組，記作D，其中（1）V≠?稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。（2）E為邊集，它是笛卡兒積V×V的多重子集，其元素稱為有向邊，簡稱邊。圖的一些概念和規(guī)定G表示無向圖，但有時(shí)用G泛指圖(無向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。若

7、V(G)

8、＝n，則稱G為n階圖。若

9、V(G)

10、與

11、E(G)

12、均為有限數(shù)，則稱G為有限圖。若邊集E

13、(G)＝?，則稱G為零圖，此時(shí)，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖(trivialgraph)。關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn)設(shè)G＝為無向圖，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＝為有向圖，ek＝∈E，稱vi,vj為ek的端點(diǎn)。若vi＝vj，則稱ek為D中的環(huán)。無論在無向圖中還是在有向圖中

14、，無邊關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)(isolatedvertices)。相鄰與鄰接設(shè)無向圖G＝，vi，vj∈V，ek，el∈E。若?et∈E，使得et＝(vi，vj)，則稱vi與vj是相鄰的。若ek與el至少有一個(gè)公共端點(diǎn)，則稱ek與el是相鄰的。設(shè)有向圖D＝，vi，vj∈V，ek，el∈E。若?et∈E，使得et＝，則稱vi為et的始點(diǎn)，vj為et的終點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi。