[離散數(shù)學(xué)]圖論

《[離散數(shù)學(xué)]圖論》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、童夢(mèng)無(wú)憂網(wǎng)試管嬰兒論壇www.tm51.com本文由rnysun貢獻(xiàn)ppt文檔可能在WAP端瀏覽體驗(yàn)不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機(jī)查看。第八章圖論圖論(GraphTheory)圖論是個(gè)應(yīng)用十分廣泛而又極其有趣數(shù)學(xué)分支,物理、圖論是個(gè)應(yīng)用十分廣泛而又極其有趣數(shù)學(xué)分支物理、生物、經(jīng)濟(jì)、管理科學(xué)、信息論、學(xué)、生物、經(jīng)濟(jì)、管理科學(xué)、信息論、計(jì)算機(jī)等各個(gè)領(lǐng)域都可以找到圖論的足跡.域都可以找到圖論的足跡歷史上很多數(shù)學(xué)家對(duì)圖論的形成作出過(guò)貢獻(xiàn),歷史上很多數(shù)學(xué)家對(duì)圖論的形成作出過(guò)貢獻(xiàn)特別要提與凱萊(Cayley).到的歐拉(Euler)、基爾霍夫、基爾霍夫(Kirchhoff)與凱萊與

2、凱萊歐拉在1736年發(fā)表了第一篇圖論的論文解決了著名的年發(fā)表了第一篇圖論的論文,歐拉在年發(fā)表了第一篇圖論的論文七橋問(wèn)題.拓?fù)鋵W(xué)中著名的歐拉公式,也是圖論中的重要七橋問(wèn)題拓?fù)鋵W(xué)中著名的歐拉公式也是圖論中的重要公式.公式基爾霍夫?qū)﹄娐肪W(wǎng)絡(luò)的研究(基爾霍夫定律基爾霍夫定律)以及凱萊在基爾霍夫?qū)﹄娐肪W(wǎng)絡(luò)的研究基爾霍夫定律以及凱萊在有機(jī)化學(xué)計(jì)算中應(yīng)用了樹和生成樹等概念.有機(jī)化學(xué)計(jì)算中應(yīng)用了樹和生成樹等概念很多有趣的數(shù)學(xué)游戲也促進(jìn)了圖論的發(fā)展,如漢米爾頓很多有趣的數(shù)學(xué)游戲也促進(jìn)了圖論的發(fā)展如漢米爾頓周游世界游戲,四色定理等,都促進(jìn)了圖論的發(fā)展.周游世界游戲四色定理等都促進(jìn)了圖論的發(fā)展8-1.圖的基

3、本概念多用戶操作系統(tǒng)中的進(jìn)程狀態(tài)變換圖:例1.多用戶操作系統(tǒng)中的進(jìn)程狀態(tài)變換圖(進(jìn)程一個(gè)業(yè)務(wù)可以分成若干個(gè)階段每個(gè)階段看成一進(jìn)程:一個(gè)業(yè)務(wù)可以分成若干個(gè)階段進(jìn)程一個(gè)業(yè)務(wù)可以分成若干個(gè)階段,每個(gè)階段看成一個(gè)進(jìn)程.一個(gè)進(jìn)程有三種狀態(tài).)個(gè)進(jìn)程一個(gè)進(jìn)程有三種狀態(tài)進(jìn)程調(diào)度re執(zhí)行e就緒rI/O完成等待w請(qǐng)求I/OV={r,e,w}E={,,}w就緒狀態(tài):進(jìn)程具備執(zhí)行條件因就緒狀態(tài)進(jìn)程具備執(zhí)行條件,因CPU少,要排隊(duì)等待分配進(jìn)程具備執(zhí)行條件少要排隊(duì)等待分配CPU.執(zhí)行狀態(tài):進(jìn)程已經(jīng)分配到進(jìn)程已經(jīng)分配到CPU,它的程序正被執(zhí)行它的程序正被執(zhí)行.執(zhí)行狀態(tài)進(jìn)程已經(jīng)分配到它

4、的程序正被執(zhí)行等待狀態(tài):進(jìn)程等待某事件進(jìn)程等待某事件(如完成此時(shí)就是給它CPU完成),此時(shí)就是給它等待狀態(tài)進(jìn)程等待某事件如I/O完成此時(shí)就是給它也不能執(zhí)行..也不能執(zhí)行七橋問(wèn)題”哥尼斯堡城內(nèi)有一條河普例2.“七橋問(wèn)題”十八世紀(jì)哥尼斯堡城內(nèi)有一條河普七橋問(wèn)題十八世紀(jì),哥尼斯堡城內(nèi)有一條河雷格爾河,河中有兩個(gè)島嶼河面架有七座橋,使得島嶼與兩格爾河河中有兩個(gè)島嶼,河面架有七座橋使得島嶼與兩河中有兩個(gè)島嶼河面架有七座橋A岸之間互相貫通.岸之間互相貫通ABCDe1ee52Be6e3e4e7CDV={A,B,C,D}E={e1,e2,e3,e4,e5e6,e7}人們茶余飯后經(jīng)常到橋上散步,從而提出

5、這樣問(wèn)題從而提出這樣問(wèn)題:是否人們茶余飯后經(jīng)常到橋上散步從而提出這樣問(wèn)題是否可以從某地出發(fā)，每座橋都走一次,再回到出發(fā)點(diǎn)再回到出發(fā)點(diǎn).可以從某地出發(fā)，每座橋都走一次再回到出發(fā)點(diǎn)很多人試圖找出這樣的路徑,都沒(méi)有找到.人試圖找出這樣的路徑都沒(méi)有找到后來(lái)歐拉證明這樣的路徑根本不存在.的路徑根本不存在此圖可以抽象為上邊右圖.此圖可以抽象為上邊右圖在機(jī)械加工中,經(jīng)常需要在一塊金屬薄板上鉆若干孔例3.在機(jī)械加工中經(jīng)常需要在一塊金屬薄板上鉆若干孔(或者是機(jī)械手在印刷電路板上安裝電子元件如圖所示或者是機(jī)械手在印刷電路板上安裝電子元件)如圖所示或者是機(jī)械手在印刷電路板上安裝電子元件如圖所示:5273問(wèn)如

6、何確定鉆孔的次序,使之加工的時(shí)間最短問(wèn)如何確定鉆孔的次序使之加工的時(shí)間最短.使之加工的時(shí)間最短這個(gè)問(wèn)題可以抽象為在一個(gè)圖上求從某一個(gè)結(jié)點(diǎn)出發(fā),這個(gè)問(wèn)題可以抽象為在一個(gè)圖上求從某一個(gè)結(jié)點(diǎn)出發(fā)經(jīng)過(guò)所有結(jié)點(diǎn)一次,使得此路徑最短.如何找到此路徑.經(jīng)過(guò)所有結(jié)點(diǎn)一次使得此路徑最短如何找到此路徑類似的:旅行最優(yōu)問(wèn)題,工程最優(yōu)問(wèn)題,成本(費(fèi)用最低.費(fèi)用)最低類似的旅行最優(yōu)問(wèn)題工程最優(yōu)問(wèn)題成本費(fèi)用最低………一.圖的概念一個(gè)圖G=,其中V(G):是G的結(jié)點(diǎn)的非空集合(V(G)≠Φ),簡(jiǎn)記成的結(jié)點(diǎn)的非空集合.簡(jiǎn)記成V.的結(jié)點(diǎn)的非空集合簡(jiǎn)記成E(G):是G的邊的集合有時(shí)簡(jiǎn)記成的邊的集合.

7、的邊的集合有時(shí)簡(jiǎn)記成E.?結(jié)點(diǎn)結(jié)點(diǎn)(Vertices):用表示旁邊標(biāo)上該結(jié)點(diǎn)的名稱表示,旁邊標(biāo)上該結(jié)點(diǎn)的名稱.?邊(Edges):有向邊:帶箭頭的弧線.從u到v的邊表示成有向邊帶箭頭的弧線到的邊表示成的邊無(wú)向邊:不帶箭頭的弧線和間的邊不帶箭頭的弧線.間的邊表示成無(wú)向邊不帶箭頭的弧線u和v間的邊表示成(u,v)Aree1ee52G1:Be6G2:Dwe3V(G1)={r,e,w}E(G1)={,,}Ce4e7V(G2