圖論模型講義

1、1目錄目錄目錄....................................................................................................................................................1第8章圖論模型.........................................................

2、.....................................................................18.1圖的基本知識(shí).....................................................................................................................28.1.1圖的相關(guān)定義............

3、.............................................................................................28.1.2圖的頂點(diǎn)的度.........................................................................................................38.1.3子圖及運(yùn)

4、算.............................................................................................................48.1.4圖的連通性...................................................................................................

5、.........58.1.5一些特殊圖.............................................................................................................78.2圖的矩陣表示.................................................................................

6、....................................78.2.1鄰接矩陣.................................................................................................................78.2.2關(guān)聯(lián)矩陣...................................................

7、.............................................................88.3圖的方法建模.....................................................................................................................98.3.1圖的最小生成樹(shù)問(wèn)題及算法..............

8、................................................................101樹(shù)及最小生成樹(shù)........................................................................................................102克魯斯卡爾算法................................

9、........................................................................113普利姆算法................................................................................................................138.3.2圖的最短路問(wèn)題及算法...........

10、............................................................................151迪克斯特拉算法........................................................................................................158.3.3圖的匹配及應(yīng)用................

11、...................................................................................201.圖的匹配....................................................................................................................202指派問(wèn)題：.....

12、...........................................................................................................233最優(yōu)指派..........................................................................................................

13、..........278.3.4圖的覆蓋及應(yīng)用..................................................................................................331.邏輯算法..........................................................................................

14、..........................352啟發(fā)式算法：............................................................................................................353利用關(guān)聯(lián)矩陣求極小覆蓋：..............................................................

15、......................378.3.5圖的遍歷問(wèn)題.......................................................................................................391邊的遍歷中國(guó)郵差問(wèn)題.....................................................................

16、.....................392點(diǎn)的遍歷旅行商問(wèn)題..............................................................................................418.3.6競(jìng)賽圖問(wèn)題.................................................................................

17、.........................491競(jìng)賽圖的定義............................................................................................................492循環(huán)比賽排名.....................................................................

18、.......................................508.4實(shí)戰(zhàn)篇...............................................................................................................................51第8章圖論模型圖論模型圖論（GraphThey）18世紀(jì)起源于歐洲。瑞士著名數(shù)學(xué)家歐拉(

19、Euler）于1736年發(fā)3鄰（adjacent）；邊稱(chēng)為與頂點(diǎn)關(guān)聯(lián)（incident）。如果某兩條邊至少有一個(gè)公共頂點(diǎn)，kejivv則稱(chēng)這兩條邊在圖中相鄰，沒(méi)有公共頂點(diǎn)的邊稱(chēng)為相互獨(dú)立的（independent）。G定義定義2：一個(gè)有向圖（digraph）是由一個(gè)非空點(diǎn)集和其中元素的有序關(guān)系集合D)(DV構(gòu)成，記為，簡(jiǎn)記為。)(DA))()((DADVD?)(AVD?稱(chēng)為有向圖的頂點(diǎn)集或節(jié)點(diǎn)集，中的每一個(gè)元素21nvvvV??DV稱(chēng)為

20、該圖的一個(gè)頂點(diǎn)或節(jié)點(diǎn)；稱(chēng)為有向圖的弧集)21(nivi??21maaaA??D（arcset），中的每一個(gè)元素(即中某兩個(gè)元素的有序?qū)?記為或AkaVjivv)(jikvva?，被稱(chēng)為該有向圖的一條從到的?。╝rc）。)21(nkvvajik???ivjv當(dāng)一條弧可表示為時(shí)，稱(chēng)為的頭（head），為的尾（tail），或者說(shuō)jikvva?ivkajvka到相鄰，從相鄰；稱(chēng)弧為的出?。╫utgoingarc），為的入?。╥ncomingiv

21、jvjvivkaivjvarc）。圖的點(diǎn)集中點(diǎn)的數(shù)量稱(chēng)作圖的階（der），邊集中邊的數(shù)量稱(chēng)作圖的邊數(shù)(size).VE當(dāng)一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱(chēng)該圖為有限圖。定義定義3：給一個(gè)圖的每一條邊（?。┵x予一個(gè)數(shù)字，則得到一個(gè)賦權(quán)圖賦權(quán)圖（weightedgraph）。這些數(shù)字可以表示距離，花費(fèi)，時(shí)間等，統(tǒng)稱(chēng)為權(quán)重(weight)。無(wú)向圖和有向圖都可以賦權(quán)。例1下面兩個(gè)圖分別是無(wú)向圖，有向圖和賦權(quán)圖。WDGGe1v1e5e2e3e3

22、v2v4v3v1Da1v4v2v3a6a2a4a5a32345Wv1v2v3v46圖2無(wú)向圖、有向圖和賦權(quán)圖只有一個(gè)頂點(diǎn)的圖稱(chēng)為平凡圖（trivialgraph），除平凡圖外所有圖都被稱(chēng)為非平凡圖。如果圖的一條邊（或者?。┑亩它c(diǎn)為同一個(gè)點(diǎn)，則稱(chēng)這條邊為環(huán)（loop）。在無(wú)向圖當(dāng)中，如果兩條邊的端點(diǎn)相同，則稱(chēng)這兩條邊為關(guān)聯(lián)這兩點(diǎn)的重邊（multiedge）。有向圖當(dāng)中，兩條弧如果端點(diǎn)和方向都相同才稱(chēng)為重邊。既沒(méi)有重邊也沒(méi)有環(huán)的圖被稱(chēng)為簡(jiǎn)單

23、圖（simplegraph）。8.1.28.1.2圖的頂點(diǎn)的度圖的頂點(diǎn)的度定義定義1：（1）在無(wú)向圖中，與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目（環(huán)算兩次）稱(chēng)為的度（degree），vv記為)(vd度為奇數(shù)的點(diǎn)稱(chēng)為奇頂點(diǎn)，度為偶數(shù)的點(diǎn)稱(chēng)為偶頂點(diǎn)。度為0的點(diǎn)稱(chēng)為孤立點(diǎn)孤立點(diǎn)（isolatedvertex），它不與任何點(diǎn)相鄰。度為1的點(diǎn)稱(chēng)為葉子點(diǎn)（leaf）。所有頂點(diǎn)度都為的簡(jiǎn)單圖被稱(chēng)為階正則圖（kregulargraph）。k)121(??Vk?k特別地，若