圖論模型講義

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

2、.....................................................................18.1圖的基本知識.....................................................................................................................28.1.1圖的相關定義............

3、.............................................................................................28.1.2圖的頂點的度.........................................................................................................38.1.3子圖及運

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

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

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

7、.............................................................88.3圖的方法建模.....................................................................................................................98.3.1圖的最小生成樹問題及算法..............

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

9、........................................................................113普利姆算法................................................................................................................138.3.2圖的最短路問題及算法...........

10、............................................................................151迪克斯特拉算法........................................................................................................158.3.3圖的匹配及應用................

11、...................................................................................201.圖的匹配....................................................................................................................202指派問題：.....

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

13、..........278.3.4圖的覆蓋及應用..................................................................................................331.邏輯算法..........................................................................................

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

15、......................378.3.5圖的遍歷問題.......................................................................................................391邊的遍歷中國郵差問題.....................................................................

16、.....................392點的遍歷旅行商問題..............................................................................................418.3.6競賽圖問題.................................................................................

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

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

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

20、該圖的一個頂點或節(jié)點；稱為有向圖的弧集)21(nivi??21maaaA??D（arcset），中的每一個元素(即中某兩個元素的有序?qū)?記為或AkaVjivv)(jikvva?，被稱為該有向圖的一條從到的?。╝rc）。)21(nkvvajik???ivjv當一條弧可表示為時，稱為的頭（head），為的尾（tail），或者說jikvva?ivkajvka到相鄰，從相鄰；稱弧為的出弧（outgoingarc），為的入弧（incomingiv

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

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

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