電子科技大學圖論

1、圖論是一個應用十分廣泛而又極其有趣的數(shù)學分支。圖論是一個應用十分廣泛而又極其有趣的數(shù)學分支。物理、化學、生物、科學管理、計算機等各個領域物理、化學、生物、科學管理、計算機等各個領域都可找到圖論的足跡。本講座主要介紹圖論的一些都可找到圖論的足跡。本講座主要介紹圖論的一些基本知識、圖論中常用的初等方法?；局R、圖論中常用的初等方法。例：可以把右圖看成是例：可以把右圖看成是一個公路網，一個公路網，v1,vl0是一些城鎮(zhèn)，每條線旁是一些城鎮(zhèn)，每條線旁邊的數(shù)字代表這一段公邊的數(shù)字代表這一段公路的長度。現(xiàn)在問，要路的長度?，F(xiàn)在問，要從從v1把貨物運到把貨物運到v10。走。走哪條路最近？這個問題哪條路最近

2、？這個問題通常叫做最短路徑問題通常叫做最短路徑問題.圖的概念圖的概念圖的概念圖的概念例例: 上圖還可看成公路網，上圖還可看成公路網，v1，v2，v10看看成公路網的一個站點，若這個公路網目前被成公路網的一個站點，若這個公路網目前被敵方占領。請分析一下，能否僅破壞其公路敵方占領。請分析一下，能否僅破壞其公路網的一個站點或者至少破壞敵人哪幾個站點網的一個站點或者至少破壞敵人哪幾個站點，就可摧毀敵方整個運輸線。，就可摧毀敵方整個運輸線。這類問題稱為圖的連通性問題這類問題稱為圖的連通性問題圖的概念圖的概念一個圖一個圖G是由一個稱為點集的非空集合是由一個稱為點集的非空集合V(G)和和一個稱為邊集的集合一

3、個稱為邊集的集合E(G)組成的有序對組成的有序對(其中其中V(G) E(G)= =f f),記為記為G=(V(G)，E(G).簡記為簡記為G=(V，E).其中其中V的元素稱為點或頂點，的元素稱為點或頂點，E的元素稱為邊，并且的元素稱為邊，并且E中的每一個元素均與中的每一個元素均與V中的一對無序點相對應（點對中的一對無序點相對應（點對中的點可以相同）。中的點可以相同）。點集與邊集均為有限集的圖稱為有限圖。點集與邊集均為有限集的圖稱為有限圖。若邊若邊e對應的無序點對為對應的無序點對為u,v，則記，則記e=uv，其中，其中u,v均稱均稱為邊為邊e的端點。的端點。若用小圓點表示點若用小圓點表示點集中的

4、點，連線表集中的點，連線表示邊，可用圖形將示邊，可用圖形將圖表示出來。圖表示出來。圖的概念圖的概念例：設例：設V=v1, v2, v3, v4，E=e1, e2, e3, e4, e5 ，滿足，滿足 e1= v1v2， e2= v2v3， e3= v2v3， e4= v3v4， e5= v4v4，則稱則稱G=（V，E）是一個圖。）是一個圖。圖的概念圖的概念例：例：設設V =v1,v2,v3,v4，E =v1v2 ,v1v2,v2v3 ，則，則H = (V,E ）是一個圖。）是一個圖。 v1v2v3v4圖的概念圖的概念若邊若邊e與無序結點對與無序結點對(u，v)相對應，則稱邊相對應，則稱邊e為為

5、無向無向邊邊,記為記為e(u，v)，這時稱，這時稱u，v是邊是邊e的兩個的兩個端點端點；若邊若邊e與有序結點對與有序結點對相對應，則稱邊相對應，則稱邊e為為有向有向邊邊(或弧或弧)，記為，記為e，這時稱，這時稱u是邊是邊e的的始點始點(或弧尾或弧尾).v是邊是邊e的的終點終點(或弧頭或弧頭)，統(tǒng)稱為，統(tǒng)稱為e的的端點端點；在一個圖中，關聯(lián)結點在一個圖中，關聯(lián)結點vi和和vj的邊的邊e，無論是有向的，無論是有向的還是無向的，均稱邊還是無向的，均稱邊e與結點與結點vi和和vj相關聯(lián)相關聯(lián)，而，而vi和和vj稱為稱為鄰接點鄰接點，否則稱為，否則稱為不鄰接的不鄰接的；關聯(lián)于同一個結點的兩條邊稱為關聯(lián)于

6、同一個結點的兩條邊稱為鄰接邊鄰接邊；圖的概念圖的概念圖中關聯(lián)同一個結點的邊稱為圖中關聯(lián)同一個結點的邊稱為自回路自回路（或（或環(huán)環(huán)）；）；圖中不與任何結點相鄰接的結點稱為圖中不與任何結點相鄰接的結點稱為孤立結點孤立結點；僅由孤立結點組成的圖稱為僅由孤立結點組成的圖稱為零圖零圖；僅含一個結點的零圖稱為僅含一個結點的零圖稱為平凡圖平凡圖；含有含有n個結點、個結點、m條邊的圖稱為條邊的圖稱為（n，m）圖）圖；每條邊都是無向邊的圖稱為每條邊都是無向邊的圖稱為無向圖無向圖；每條邊都是有向邊的圖稱為每條邊都是有向邊的圖稱為有向圖有向圖；圖的概念圖的概念有些邊是無向邊有些邊是無向邊,而另一些是有向邊的圖稱為而

7、另一些是有向邊的圖稱為混合圖混合圖.在有向圖中，兩個結點間（包括結點自身間）若有同在有向圖中，兩個結點間（包括結點自身間）若有同始點和同終點的幾條邊，則這幾條邊稱為始點和同終點的幾條邊，則這幾條邊稱為平行邊平行邊，在，在無向圖中，兩個結點間（包括結點自身間）若有幾條無向圖中，兩個結點間（包括結點自身間）若有幾條邊，則這幾條邊稱為邊，則這幾條邊稱為平行邊平行邊，兩結點，兩結點vi，vj間相互平行間相互平行的邊的條數(shù)稱為邊的邊的條數(shù)稱為邊(vi，vj）或）或的的重數(shù)重數(shù)；含有平行邊的圖稱為含有平行邊的圖稱為多重圖多重圖。非多重圖稱為。非多重圖稱為線圖線圖；無；無環(huán)的線圖稱為環(huán)的線圖稱為簡單圖簡單圖

8、。圖中頂點的個數(shù)稱為該圖的圖中頂點的個數(shù)稱為該圖的階階。任意兩點均相鄰的簡單圖稱為任意兩點均相鄰的簡單圖稱為完全圖完全圖，n階完全圖階完全圖記為記為Kn。例如。例如K2, K3, K4分別為如下圖所示分別為如下圖所示。K2K3K4圖的概念圖的概念圖的概念圖的概念簡單圖簡單圖多重圖多重圖例如：例如：平凡圖平凡圖圖的概念圖的概念賦權圖賦權圖G是一個三重組是一個三重組或四重組或四重組，其，其中，中，V是結點集合，是結點集合，E是邊的集合，是邊的集合，f是從是從V到非負實數(shù)到非負實數(shù)集合的函數(shù)，集合的函數(shù)，g是從是從E到非負實數(shù)集合的函數(shù)。到非負實數(shù)集合的函數(shù)。關聯(lián)矩陣和鄰接矩陣：關聯(lián)矩陣和鄰接矩陣：

9、設圖設圖G = (V,E)，V = v1,v2,vn，E = e1, e2,em 。G 的的關聯(lián)矩關聯(lián)矩陣陣 M(G) = mij 是一個是一個 nm 矩陣，其中矩陣，其中 mij 為點為點 vi 與邊與邊 ej 關聯(lián)的次數(shù)；關聯(lián)的次數(shù)；G的的鄰接矩鄰接矩陣陣 A(G) = aij 是一個是一個n階方陣，其中階方陣，其中aij 是連是連接接 vi 與與 vj 的邊的數(shù)目。的邊的數(shù)目。圖的概念圖的概念圖的關聯(lián)矩陣圖的關聯(lián)矩陣 M(G)=mij。其中。其中mij是點是點vi與邊與邊ej相關相關聯(lián)的次數(shù)。聯(lián)的次數(shù)。 = =21000011100011100001 )(543214321eeeeevv

10、vvGM如如右右圖圖圖的概念圖的概念圖的鄰接矩陣圖的鄰接矩陣 A(G)=aij。其中。其中aij是連接點是連接點vi與點與點vi的的邊的條數(shù)。邊的條數(shù)。 = =1100102002010010 )(43214321vvvvvvvvGA如如右右圖圖圖的概念圖的概念無環(huán)有向圖的關聯(lián)矩陣無環(huán)有向圖的關聯(lián)矩陣 M(G)=mij。其中。其中mij是點是點vi與與邊邊ej相關聯(lián)的次數(shù)（起點為相關聯(lián)的次數(shù)（起點為-1，終點為，終點為+1）。）。 = =11000011100011110001 )(543214321eeeeevvvvGM如如右右圖圖圖的概念圖的概念有向圖的鄰接矩陣有向圖的鄰接矩陣 A(G)=

11、aij。其中。其中aij是連接點是連接點vi與點與點vi的邊的條數(shù)。的邊的條數(shù)。 = =1100001001010000 )(43214321vvvvvvvvGA如如右右圖圖圖的概念圖的概念圖的同構：圖的同構：設有圖設有圖G和圖和圖G1,如果存在雙射函數(shù)如果存在雙射函數(shù)g:VV1,使得對于任意的邊使得對于任意的邊e(vi,vj)(或或) E，當且僅當，當且僅當e1(g(vi),g(vj) (或或) E1,并且并且(vi,vj)與與(g(vi),g(vj) (或或 與與) 有相同的重數(shù)。有相同的重數(shù)。則稱則稱G和和G1同構同構，記為記為G G1。圖的概念圖的概念圖的概念圖的概念例例: :如下圖所

12、示，如下圖所示，這四個圖實際上是同一個圖，因為它們是同構的。這四個圖實際上是同一個圖，因為它們是同構的。定義：設定義：設v為為G的頂點，的頂點，G中以中以v為端點的邊的條數(shù)（為端點的邊的條數(shù)（環(huán)計算兩次）稱為環(huán)計算兩次）稱為v 的度數(shù)。簡稱為的度數(shù)。簡稱為v的度，記為的度，記為dG(v)，簡記為，簡記為d(G).如右圖：如右圖：3)(, 3)(, 3)(, 1)(4321= = = = =vdvdvdvd圖的概念圖的概念注注：該圖中各點的度數(shù)之和等于該圖中各點的度數(shù)之和等于10，恰好是邊數(shù)，恰好是邊數(shù)5的的兩兩倍倍圖中圖中d (v1) = 5，d (v2) = 4 ，d (v3) = 3，d

13、(v4) = 0，d (v5) = 2。v1v2v3v4v5例：例：注注：該圖中各點的度該圖中各點的度數(shù)之和等于數(shù)之和等于14，恰好是，恰好是邊數(shù)邊數(shù)7的的兩兩倍倍圖的概念圖的概念類似有出度和入度的概念類似有出度和入度的概念)(deg),(degvv ；mvVv2)deg(= = 1 1）在無向圖）在無向圖G=V，E中，則所有結點的度數(shù)的中，則所有結點的度數(shù)的總和等于邊數(shù)的兩倍，即：總和等于邊數(shù)的兩倍，即：圖的概念圖的概念握手定理握手定理 (歐拉歐拉)證明證明 因圖因圖 G 的任一條邊均有兩個端點的任一條邊均有兩個端點 (可以相同可以相同)，在計算度時恰被計算兩次在計算度時恰被計算兩次 (每個

14、端點各被計算了一每個端點各被計算了一次次)，所以各點的度數(shù)之和恰好為邊數(shù)的兩倍，即，所以各點的度數(shù)之和恰好為邊數(shù)的兩倍，即 上上 式成立。式成立。，mvvvmvvVvVvVvVvVv2)(deg)(deg)deg()(deg)(deg= = = = = = 2 2）在有向圖）在有向圖G=V，E中，則所有結點的引出度中，則所有結點的引出度數(shù)之和等于所有結點的引入度數(shù)之和，所有結點的數(shù)之和等于所有結點的引入度數(shù)之和，所有結點的度數(shù)的總和等于邊數(shù)的兩倍，即：度數(shù)的總和等于邊數(shù)的兩倍，即：圖的概念圖的概念握手定理握手定理 (歐拉歐拉)推論推論：在圖：在圖G=V，E中，其中，其V=v1,v2 ,v3 ,

15、vn ， E=e1，e2，em，度數(shù)為奇數(shù)的，度數(shù)為奇數(shù)的結點個數(shù)為偶數(shù)。結點個數(shù)為偶數(shù)。圖的概念圖的概念圖的概念圖的概念例：例：證明在任意一次集會中和奇數(shù)個人握手的證明在任意一次集會中和奇數(shù)個人握手的人的個數(shù)為偶數(shù)個。人的個數(shù)為偶數(shù)個。證明證明: 將集會中的人作為點，若兩個人握手則將集會中的人作為點，若兩個人握手則對應的點聯(lián)邊，則得簡單圖對應的點聯(lián)邊，則得簡單圖G。這樣。這樣G中點中點v的的度對應于集會中與度對應于集會中與v握手的人的個數(shù)。于是，握手的人的個數(shù)。于是，問題轉化為證明問題轉化為證明“任意圖中度數(shù)為奇的點的個任意圖中度數(shù)為奇的點的個數(shù)為偶數(shù)數(shù)為偶數(shù)”，這正是，這正是推論推論的結論

16、。的結論。定義定義：在圖：在圖G中，一個由不同的邊組成的序列中，一個由不同的邊組成的序列e1, e2, en，如果，如果ei是連接是連接vi-1與與vi (il,2,n)的，并且的，并且ei-1與與ei (il,2,n-1)相鄰。我們就稱這個序列為從相鄰。我們就稱這個序列為從v0到到vn的的一條一條通路通路(或道路或道路)，數(shù)，數(shù)n稱為路長，稱為路長， v0和和vn稱為這條道稱為這條道路的兩個端點，路的兩個端點， vi(1in)叫做道路的內點。如果叫做道路的內點。如果G是簡單圖，這條道路也可以記作是簡單圖，這條道路也可以記作(v0 ， v0 ， vn)。邊不重復的通路稱為邊不重復的通路稱為簡單

17、通路簡單通路。除了端點可相同外，任意兩點都不相同的通路稱為除了端點可相同外，任意兩點都不相同的通路稱為基基本通路本通路。顯然它一定是簡單通路。顯然它一定是簡單通路。最短路問題最短路問題 起點和終點相同的通路稱為起點和終點相同的通路稱為回路回路。邊不重復的回路稱為邊不重復的回路稱為簡單回路簡單回路。起點和終點相同的長為正的基本通路稱為起點和終點相同的長為正的基本通路稱為基基本回路本回路，簡稱，簡稱圈圈。定義定義：給定圖：給定圖G=(V,E)，對，對u,vV,若若u與與v間間存在通路，則稱存在通路，則稱u與與v間的最短通路的長為從間的最短通路的長為從u到到v的距離，記為的距離，記為d(u,v),若

18、若u與與v間不存在通間不存在通路，則稱從路，則稱從u到到v的距離為無窮。的距離為無窮。最短路問題最短路問題 例：如右圖例：如右圖6v5v4v3v2v1v1e9e8e7e6e5e4e3e2ev1v2v5v1v2v3v6是通路是通路v1v2v5v1v4v5v6是簡單是簡單通路通路v1v5v2v6是基本通路是基本通路v1v2v5v1v2v3v6v5v1是回路是回路v1v4v5v6v2v5v1是簡單回路是簡單回路v1v2v3v6v5v4v1是基本回路是基本回路最短路問題最短路問題 例：考慮右圖例：考慮右圖（1,2,3）是基本通路）是基本通路（1,1,1,2,3）是通路）是通路（1,2,4,1,4,3）

19、是簡單通路）是簡單通路（1,2,4,1,4,3,1）是回路）是回路（1,2,4,1,2,3,1）是簡單回路）是簡單回路（1,2,4,3,1）是基本回路）是基本回路最短路問題最短路問題 例例:在下圖在下圖G中，取中，取1 = v1v2v3 ，2 = v1v2v3v4v2 ，3 = v1v2v3v2v3v4 ( 注：注：簡單圖可只用點序列表通路）簡單圖可只用點序列表通路）v1v4v5v3v2G則則 1, 2, 3 依次為長為依次為長為2,4,5的通路，其中的通路，其中1與與2為簡單通路，為簡單通路，1為基為基本通路。本通路。 由定義由定義1可看出可看出,G中中 v1v2v5v1為長為為長為3的圈，

20、的圈，v1v2v3v4v2 v5v1為長為為長為6的簡單回路。的簡單回路。最短路問題最短路問題 最短路問題最短路問題 注：注：在回路已被定義為通路的特殊情況中，為了討在回路已被定義為通路的特殊情況中，為了討論問題的方便，我們約定：論問題的方便，我們約定：凡指基本通路或路均認凡指基本通路或路均認為此路不是圈。為此路不是圈。易知，圖中若點易知，圖中若點u與與 v間存在通路，則間存在通路，則 u 與與 v 間必存間必存在基本通路；若過點在基本通路；若過點u存在簡單回路，則過點存在簡單回路，則過點u必存必存在基本回路。在基本回路。定義定義:給定圖給定圖G = (V, E)，對，對 u, vV，若，若u

21、與與 v間存在間存在通路，則稱通路，則稱u與與 v間的最短通路的長為從間的最短通路的長為從u到到 v的距離，的距離，記為記為 d(u, v)；若；若u與與 v間不存在通路，則稱從間不存在通路，則稱從u到到 v的的距離為無窮。距離為無窮。例如右圖：例如右圖： d(u, v) = 2其最短路為其最短路為uxvuvwxd(u, w) = 容易證明對容易證明對 ，距離具有性質：，距離具有性質：（1）d(u, v)0；（；（2）d(u, v) = d(v, u)；（3）d(u, v) + d(v, w) d(u, w)最短路問題最短路問題 連連通通圖圖 G D任意兩點間均存在通路的圖稱為任意兩點間均存在

22、通路的圖稱為連通圖連通圖，否則稱為，否則稱為非連非連通圖通圖。若若H是圖是圖G 的連通子圖且的連通子圖且H不能再擴充為不能再擴充為G的任一連的任一連通子圖，則稱通子圖，則稱H為為G的連通分支。用的連通分支。用(G) 記圖記圖G 的連的連通分支數(shù)。通分支數(shù)。非非連連通通圖圖 例如：例如：(D) =3， (G) =1 最短路問題最短路問題 定義：定義：若圖若圖G的每一條邊的每一條邊e都附有一個實數(shù)都附有一個實數(shù)w(e)，則，則稱稱G為為權圖權圖。實數(shù)。實數(shù)w(e) 稱為稱為e的權。子圖的權。子圖H的各邊權的各邊權之和稱為子圖之和稱為子圖H的權，記為的權，記為W(H)。例如下圖例如下圖G為權圖，其中

23、為權圖，其中w(v1v2) = 1，w(v1v3) = 5，W(G) = 20。v1v3v2v4 G 1 3 5 6 5最短路問題最短路問題 設設是權圖是權圖G中的一條路，稱中的一條路，稱的各邊權之和為路的各邊權之和為路的的長。易知，各邊的權均為長。易知，各邊的權均為1的權圖中的路長與非權圖的權圖中的路長與非權圖中的路長是一致的。中的路長是一致的。權圖中點權圖中點u到到v的距離仍定義為點的距離仍定義為點u到到v的最短路的長，的最短路的長，仍記為仍記為d(u,v)。例：例：下圖中，下圖中，d(v2, v4) = 5，相應的最短路為，相應的最短路為：v2v1 v3v4。v1v3v2v4 G 1 3

24、 1 6 3最短路問題最短路問題 例（渡河問題）例（渡河問題）:一個擺渡人要把一只狼、一只羊和一個擺渡人要把一只狼、一只羊和一捆菜運過河去。由于船很小，每次擺渡人至多只一捆菜運過河去。由于船很小，每次擺渡人至多只能帶一樣東西。另外，如果人不在旁時，狼就要吃能帶一樣東西。另外，如果人不在旁時，狼就要吃羊，羊就要吃菜。問這人怎樣才能安全地將它們運羊，羊就要吃菜。問這人怎樣才能安全地將它們運過河去？過河去？解：用解：用F表示擺渡人表示擺渡人,W表示狼表示狼,S表示羊表示羊,C表示菜表示菜.原岸全部可能出現(xiàn)的狀態(tài)為以下原岸全部可能出現(xiàn)的狀態(tài)為以下16種：種： FWSC, FWS, FWC, FSC,

25、WSC(), FW（ ）, FS, FC（ ）, WS (), WC, SC(), F （ ）, W, S, C , .最短路問題最短路問題 構造一個圖構造一個圖G，它的頂點就是剩下的，它的頂點就是剩下的10種情況。連種情況。連邊有規(guī)則是：如果經過一次渡河，情況甲可以變成邊有規(guī)則是：如果經過一次渡河，情況甲可以變成情況乙，那么就在情況甲與情況乙之間連一條邊情況乙，那么就在情況甲與情況乙之間連一條邊(如如上圖上圖)。作了圖。作了圖G以后，渡河的問題就歸結為下述問以后，渡河的問題就歸結為下述問題了：在題了：在G中找一條連接頂點中找一條連接頂點FWSC和和ff，并且包，并且包含邊數(shù)最少的路。含邊數(shù)最

26、少的路。最短路問題最短路問題 最短路問題定義：最短路問題定義：求有向圖的最短路問題求有向圖的最短路問題設設G(V,E)是一個有向圖，它的每一條弧是一個有向圖，它的每一條弧Ai都有一個都有一個非負的長度非負的長度L(Ai)，在，在G中指定一個頂點中指定一個頂點u，要求把從，要求把從u到到G的每一個頂點的每一個頂點v的最短有向路找出來的最短有向路找出來(或者指出或者指出不存在從不存在從u到到v的有向路，認為不可達的有向路，認為不可達v).求無向圖的最短路問題求無向圖的最短路問題 設設G(V,E)是一個無向圖，它的每一條邊是一個無向圖，它的每一條邊Ai都有一都有一個非負的長度個非負的長度L(Ai)，

27、在，在G中指定一個頂點中指定一個頂點u，要求把，要求把從從u到到G的每一個頂點的每一個頂點v的最短無向路找出來的最短無向路找出來(或者指或者指出不存在從出不存在從u到到v的無向路，即認不可達的無向路，即認不可達v).最短路問題最短路問題 算法算法（Dijkstra算法或標號法）算法或標號法）給定簡單權圖給定簡單權圖G=（V，E），設），設|V|=n，求，求u0到到G中中各點的距離。各點的距離。2若若i=n-1，則停；否則令，則停；否則令 ，轉（，轉（3）iiSVS= =3對每一個對每一個 ，令，令iSv vlvuwulvlvliSvii)(min ),()(),(min)( = =計算計算并用

28、并用ui+1記達最小值的某點。置記達最小值的某點。置Si+1=Siui+1，i=i+1，轉（，轉（2）。）。最短路問題最短路問題 1置置l(u0)=0；對所有；對所有vVu0，令，令l(v)=；S0=u0，i=0。說明：說明： （1 1） 算法中算法中w(ui，v) 表示邊表示邊 uiv 的權；的權； （2 2） 若只想確定若只想確定u0到某頂點到某頂點v0的距離，的距離， 則當某則當某uj等于等于v0 時即停；時即停；（3 3）算法稍加改進可同時得出）算法稍加改進可同時得出u0到其它點到其它點的最短路。的最短路。最短路問題最短路問題 例：求右圖例：求右圖u0到其到其它點的距離。它點的距離。0

29、u713851452解：解：第第1步：初始標號步：初始標號0,)(, 0)(0000= = = = = =iuSSVvvlul)0 ,(0u713851452 最短路問題最短路問題 第二步：計算第二步：計算l(v)0,(0u713851452274 第三步：求第三步：求ui+1),()(),(min)(vuwulvlvlii = =1,)(min 101= = = iuuS vliSv)0,(0u713851452)2,(1u74 最短路問題最短路問題 類似地。類似地。)0,(0u713851452)2,(1u7377)0,(0u713851452)2,(1u7)3,(2u77最短路問題最短路

30、問題 )0,(0u713851452)2,(1u6)3,(2u47)0,(0u713851452)2,(1u6)3,(2u)4,(3u7最短路問題最短路問題 )0,(0u713851452)2,(1u)6,(4u)3,(2u)4,(3u7)0,(0u713851452)2,(1u)6,(4u)3,(2u)4,(3u)7,(5u最短路問題最短路問題 另：最短路的規(guī)劃算法另：最短路的規(guī)劃算法假設圖假設圖G(V,E)有有n個頂點個頂點, 現(xiàn)要求從頂點現(xiàn)要求從頂點1到到頂點頂點n的最短路的最短路. 設決策變量為設決策變量為xij,當當xij =1時時,說明說明弧弧(i, j)位于頂點位于頂點1到頂點到

31、頂點n的最短路上的最短路上; 否則否則xij =0. 其數(shù)學規(guī)劃的表達式為其數(shù)學規(guī)劃的表達式為: Ejiijijxw),(minEjixniniixxthatsuchijnEjijjinEjijij = = = = = = = = =),(, 0, 10111),(1),(1求最短路的應用求最短路的應用例：在縱橫交錯的公路網中例：在縱橫交錯的公路網中,貨車司機希望找到一貨車司機希望找到一條從一個城市到另一個城市的最短路條從一個城市到另一個城市的最短路.假設下圖表假設下圖表示的是該公路網示的是該公路網,節(jié)點是表示貨車可以?？康某鞘泄?jié)點是表示貨車可以?？康某鞘?弧上的權表示兩個城市之間的距離弧上的

32、權表示兩個城市之間的距離(百公里百公里),那么那么從城市從城市S出發(fā)到城市出發(fā)到城市T,如何選擇行駛路線如何選擇行駛路線,使經過使經過的路程最短的路程最短?S713851452T求最短路的應用求最短路的應用解：對頂點編號解：對頂點編號S=1,T=6找到各邊的權找到各邊的權 = =018050100314800050030007515002040720wS713851452T235461決策變量為決策變量為0 ijx求最短路的應用求最短路的應用! 這是一個求最短路的這是一個求最短路的LINGO示范程序示范程序;sets:! 這是六個城市的集合這是六個城市的集合; cities/1, 2, 3,

33、4, 5, 6/; ! 城市之間存在的路由為城市集合的派生集合城市之間存在的路由為城市集合的派生集合; roads(cities, cities)/ 1,2 1,5 1,3 2,4 2,6 2,5 3,5 4,6 5,6 2,1 5,1 3,1 4,2 6,2 5,2 5,3 6,4 6,5/: w, x;endsets求最短路的應用求最短路的應用data: ! 對應城市之間路的長度對應城市之間路的長度; w = 2 4 7 5 5 1 3 8 1 2 4 7 5 5 1 3 8 1;enddatan=size(cities); ! 城市的個數(shù)城市的個數(shù);min=sum(roads: w*x)

34、;for(cities(i) | i #ne# 1 #and# i #ne# n: sum(roads(i,j): x(i,j) = sum(roads(j,i): x(j,i);sum(roads(i,j)|i #eq# 1 : x(i,j)=1;sum(roads(i,j)|j #eq# n : x(i,j)=1;for(roads:BIN(x);end求最短路的應用求最短路的應用解得：解得：Global optimal solution found. Objective value: 4.000000求最短路的應用求最短路的應用X( 1, 2) 1.000000 X( 2, 5) 1.0

35、00000X( 5, 6) 1.000000其余的其余的 X 全部取零全部取零例例:某公司在六個城市某公司在六個城市x1, x2, x3, x4, x5, x6中都設中都設有分公司從有分公司從xi,到到xj, 直接航程票價由下列矩直接航程票價由下列矩陣的第陣的第(i，j)個元素給出個元素給出(表示無直達航線表示無直達航線)請你為該公司制作一張任意兩城市之間的最請你為該公司制作一張任意兩城市之間的最廉價路線表廉價路線表最短路問題最短路問題 最短路問題最短路問題 例：設備更新問題例：設備更新問題 企業(yè)在使用某設備時，每年年初可購置新設備，企業(yè)在使用某設備時，每年年初可購置新設備，也可以使用一年或幾

36、年后賣掉重新購置新設備。已也可以使用一年或幾年后賣掉重新購置新設備。已知知4年年初購置新設備的價格分別為年年初購置新設備的價格分別為2.5、2.6、2.8和和3.1萬元。設備使用了萬元。設備使用了14年后設備的殘值分別為年后設備的殘值分別為2、1.6、1.3和和1.1萬元，使用時間在萬元，使用時間在14年內的維修年內的維修保養(yǎng)費用分別為保養(yǎng)費用分別為0.3、0.8、1.5和和2.0萬元。試確定一萬元。試確定一個設備更新策略，在下例兩種情形下使個設備更新策略，在下例兩種情形下使4年的設備年的設備購置和維護總費用最小。購置和維護總費用最小。（1）第）第4年年末設備一定處理掉；年年末設備一定處理掉；

37、（2）第）第4年年末設備不處理。年年末設備不處理。上面的數(shù)據(jù)可整理如下表：上面的數(shù)據(jù)可整理如下表： 最短路問題最短路問題 年數(shù)年數(shù)第一年第一年第二年第二年第三年第三年第四年第四年購置價格購置價格2.52.52.62.62.82.83.13.1維修保養(yǎng)費維修保養(yǎng)費0.30.30.80.81.51.52.02.0使用殘值使用殘值2 21.61.61.31.31.11.1 用點用點(1,2,3,4,5)表示第表示第1年年初購置設備使用到第年年初購置設備使用到第i年年初更新，經過若干次更新使用到第年年初更新，經過若干次更新使用到第5年年初，年年初，第第1年年初和第年年初和第5年年初分別用及表示。使用過

38、年年初分別用及表示。使用過程用弧連接起來，弧上的權表示總費用程用弧連接起來，弧上的權表示總費用(購置費維購置費維護費殘值護費殘值)，如圖所示，如圖所示 最短路問題最短路問題 154322.5+0.3-22.5+0.3+0.8-1.62.5+0.3+0.8+1.5-1.32.5+0.3+0.8+1.5+2.0-1.12.6+0.3-22.8+0.3-23.1+0.3-22.6+0.3+0.8-1.62.8+0.3+0.8-1.62.6+0.3+0.8+1.5-1.3最短路問題最短路問題 154320.823.860.92.93.22.12.33.9例：求圖的中心例：求圖的中心如學校的選址問題。如

39、學校的選址問題。最短路問題最短路問題 圖的概念圖的概念子圖的定義：子圖的定義：設有圖設有圖G和圖和圖G1,若若G和和G1滿足：滿足：1)若若V1 V，E1 E, 則稱則稱G1是是G的的子圖子圖, 記為記為G1 G;2)若若G1 G, 且且G1 G（即（即V1 V或或E1 E）, 則稱則稱G1是是G的的真子圖真子圖, 記為記為G1 G;即即V1=V, 則稱則稱G1是是G的的生成子圖生成子圖3)若若V2 V, V2 ,以以V2為結點集為結點集,以兩個端點均在以兩個端點均在V2中中的邊的全體為邊集的的邊的全體為邊集的G的子圖稱為的子圖稱為V2導出的子圖導出的子圖, 簡簡稱稱G的的(點點)導出子圖導出

40、子圖.圖的概念圖的概念4)若若E2 E，E2 ，以，以E2為邊集，以為邊集，以E2相關聯(lián)的頂點相關聯(lián)的頂點的全體為頂點集的的全體為頂點集的G的子圖稱為的子圖稱為E2導出的子圖導出的子圖，簡，簡稱稱G的的(邊邊)導出子圖導出子圖。5)設設G為具有為具有n個結點的簡單圖個結點的簡單圖, 從完全圖從完全圖Kn中刪去中刪去G中的所有的邊而得到的圖稱為中的所有的邊而得到的圖稱為G的的補圖補圖（或或G的的補補），），記為記為G。6)設設G為具有為具有n個結點的簡單圖，圖個結點的簡單圖，圖 G1 是是G的一個子圖，從圖的一個子圖，從圖G中刪去中刪去G1中的所中的所有的邊而得到的圖稱為有的邊而得到的圖稱為G1

41、相對于相對于G的的補圖補圖（或或G1在在G中的中的補補）。在下圖中，給出了圖在下圖中，給出了圖G以及它的真子圖以及它的真子圖G和生成子和生成子圖圖G”. G1是結點集是結點集v1，v2，v3，v4，v5的導出子圖的導出子圖圖的概念圖的概念在下圖中，給出了圖在下圖中，給出了圖G以及它的真子圖以及它的真子圖G和子圖和子圖G”. 其中其中G”是是G在在G中的補圖中的補圖圖的概念圖的概念樹樹樹的定義：樹的定義：無圈的連通圖稱為樹。樹中度為無圈的連通圖稱為樹。樹中度為1 1的點稱為樹葉，其余點稱為分枝點。的點稱為樹葉，其余點稱為分枝點。樹樹樹樹不是樹不是樹不是樹不是樹例例平凡樹平凡樹定理：定理：設設G是

42、具有是具有n個點個點m條邊的圖，則以下條邊的圖，則以下關于樹的命題等價。關于樹的命題等價。（1）G是樹。是樹。（2）G 中任意兩個不同點之間存在唯一的路。中任意兩個不同點之間存在唯一的路。（3）G 連通，刪去任一邊便不連通。連通，刪去任一邊便不連通。（4）G 連通，且連通，且n = m+1。（5）G 無圈，且無圈，且n= m+1。（6）G 無圈，添加任一條邊可得唯一的圈。無圈，添加任一條邊可得唯一的圈。樹樹（2）G中任意兩個不同點之間存在唯一的路中任意兩個不同點之間存在唯一的路（1）G 是是樹樹 因因G是樹，樹是連通的，故是樹，樹是連通的，故G中任意兩個不同點之中任意兩個不同點之間存在路。下證

43、唯一性。間存在路。下證唯一性。 若不然，設點若不然，設點u與與v之間存在兩條不同的路之間存在兩條不同的路1與與2。從從u出發(fā)沿出發(fā)沿1搜索，設搜索，設x是具有第一個如下性質的點：是具有第一個如下性質的點：它在它在2上，但它的下一個點上，但它的下一個點w不在不在2上；繼續(xù)搜索，上；繼續(xù)搜索，設設y是是w之后的第一個既在之后的第一個既在1上又在上又在2上的點。這樣上的點。這樣1上從上從x到到y(tǒng)段與段與2上從上從y到到x段便構成一個圈，這與段便構成一個圈，這與G是樹無圈矛盾，所以任意兩點間的路唯一。是樹無圈矛盾，所以任意兩點間的路唯一。樹樹（4）G 連通，且連通，且n= m+1“G 連通，刪去任一邊

44、便不連通連通，刪去任一邊便不連通只需證只需證 n= m+1即可。對即可。對n用歸納法。用歸納法。當當n = 1時，時，G無邊，滿足無邊，滿足n = m+1。設對少于設對少于n個點的圖（個點的圖（4）的結論成立。）的結論成立。對于有對于有n個點的圖個點的圖G，由（，由（3）的假設知刪去）的假設知刪去G中某邊可得中某邊可得兩個具有同樣性質的子圖兩個具有同樣性質的子圖G1與與G2。設。設Gi 的點數(shù)與邊數(shù)分別的點數(shù)與邊數(shù)分別為為ni 與與mi（i =1,2）。顯然）。顯然n1 n，n2 (G) 的點的點v為為割點割點。易知，若。易知，若v是是G的割點，則的割點，則v是是G的的1-頂點割頂點割。例如對

45、上例中的例如對上例中的G， V= v3, v6是是2-頂點割，頂點割，v5是割點。是割點。樹樹v1v2v3v6v5v4e1e2e3e4e5e6定義：定義：給定給定 n 階圖階圖 G，若，若 G 中存在兩個不相鄰的中存在兩個不相鄰的頂點，則令頂點，則令(G) = minkG中存在中存在k頂點割頂點割，否，否則，令則，令(G) = n 1。稱稱 (G) 為圖為圖 G 的的連通度連通度，簡記，簡記 (G) 為為 。若。若 (G)k，則稱，則稱 G 為為 k 連通的連通的。由定義由定義2，若，若G不連通或不連通或G是平凡圖，則是平凡圖，則=0。樹樹樹樹G1G3G4G2u(G1) =(G2) =1(G3

46、) =2(G4) = 4滿足滿足 (G - e) (G) 的邊的邊 e 稱為稱為 G 的割邊。的割邊。定義定義3 給定圖給定圖G，設，設S為為V(G) 的非空子集，令的非空子集，令 S, 表示表示G中兩端點分屬于中兩端點分屬于 S 與與 的邊組成的集的邊組成的集合，則稱合，則稱 S, 為為G的邊割，其中的邊割，其中 = (G)S。SSSS例如非平凡樹中每條邊均為割邊。邊割是割邊的推例如非平凡樹中每條邊均為割邊。邊割是割邊的推廣。當廣。當G連通時，邊割是指刪去一組邊使連通時，邊割是指刪去一組邊使G不連通的不連通的這組邊構成的集合。這組邊構成的集合。樹樹定義：定義：若若G 為非平凡圖，令為非平凡圖

47、，令 (G) = minkG 中存在中存在 k 邊割邊割 否則令否則令 (G)=0則稱則稱 (G)（簡記為（簡記為 ）為）為G 的邊連通度。的邊連通度。若若 (G) k，則稱，則稱G為為k 邊連通的。邊連通的。樹樹樹樹G1G3G4G2u(G1) =1 ，(G2) =2(G3) =2(G4) = 4例定理：定理：任意的圖均滿足：任意的圖均滿足： 。是顯然的，是顯然的， 的證明從略。的證明從略。也存在滿足也存在滿足 = level(i) + x(i,j) - (n-2)*(1-x(i,j) + (n-3)*x(j,i); );! The level of city is at least 1 bu

48、t no more n-1, and is 1 if it links to base (city 1); bnd(1,level(i),999); level(i) 1 =|V |可驗證彼得森圖（下圖（可驗證彼得森圖（下圖（b b）所示）不是哈密爾頓圖，）所示）不是哈密爾頓圖，但滿足定理的條件。這表明定理所給出的條件只是但滿足定理的條件。這表明定理所給出的條件只是哈密爾頓圖的必要條件而不是充分條件。哈密爾頓圖的必要條件而不是充分條件。 (b)歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 （a）v設設G是具有是具有n 個點的簡單圖，則對個點的簡單圖，則對G的任意兩個的任意兩個不相鄰頂點不相鄰頂點 u

49、和和 v ，（1）若）若d(u) + d(v)n-1, 則則 G 有有哈密爾頓路哈密爾頓路；（2）若）若d(u) + d(v)n, 則則 G 是是哈密爾頓圖哈密爾頓圖。由定理可知當由定理可知當n3時，時， Kn是哈密爾頓圖。是哈密爾頓圖。是哈密爾頓圖，是哈密爾頓圖，但不滿足定理的條件但不滿足定理的條件故該定理的條件是哈密爾頓圖的充分條件，但不是故該定理的條件是哈密爾頓圖的充分條件，但不是必要條件。必要條件。歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 說明：判斷一個圖是否哈密爾頓圖，往往要結合定義說明：判斷一個圖是否哈密爾頓圖，往往要結合定義進行。由定義知：一個圖若有度為進行。由定義知：一個圖若有度為

50、1 1的頂點，一定不的頂點，一定不是哈密爾頓圖，只可能有哈密爾頓路；若圖是哈密爾是哈密爾頓圖，只可能有哈密爾頓路；若圖是哈密爾頓圖，則圖中頓圖，則圖中2 2度頂點關聯(lián)的邊必屬于所有哈密爾頓度頂點關聯(lián)的邊必屬于所有哈密爾頓圈；一個頂點關聯(lián)的邊再多，一個哈密爾頓圈只能用圈；一個頂點關聯(lián)的邊再多，一個哈密爾頓圈只能用其兩條邊。其兩條邊。左圖不是哈密爾頓圖，左圖不是哈密爾頓圖，因圖中二度頂點所關聯(lián)因圖中二度頂點所關聯(lián)的的8 8條邊（紅邊）已構條邊（紅邊）已構成圈，而此圈不是哈密成圈，而此圈不是哈密爾頓圈。爾頓圈。歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 問題：問題：一個旅行售貨員想訪問若干城市（假定一個旅

51、行售貨員想訪問若干城市（假定各城鎮(zhèn)之間均有路可通），然后返回。問如何各城鎮(zhèn)之間均有路可通），然后返回。問如何安排路線使其能恰好訪問每個城鎮(zhèn)一次且走過安排路線使其能恰好訪問每個城鎮(zhèn)一次且走過的總路程最短？這個問題稱為旅行售貨員問題，的總路程最短？這個問題稱為旅行售貨員問題，它的圖論模型為：在賦權完全圖它的圖論模型為：在賦權完全圖G中求具有最中求具有最小權的哈密爾頓圈，這個圈稱為小權的哈密爾頓圈，這個圈稱為最優(yōu)圈最優(yōu)圈。求最優(yōu)圈，目前還沒有一個理想的算法。求最優(yōu)圈，目前還沒有一個理想的算法。歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 一個可行解法：一個可行解法： （1）任?。┤稳 的一個哈密爾頓圈的一

52、個哈密爾頓圈C。 （2）修改修改 C 為為 Cij 使使Cij 比比 C 優(yōu)，其方法為：設優(yōu)，其方法為：設 C = v1 v2vn v1，若存在整數(shù)，若存在整數(shù) i，j，滿足滿足0 i+1j 23 = w (cd) + w(ab) 取取 C = b c d a b如圖（如圖（c）所示）所示(a) bacd10181171412歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 (b) bacd10181171412(c) bacd10181171412另：最優(yōu)另：最優(yōu)Hamilton圈規(guī)劃表達式圈規(guī)劃表達式設設 dij 是兩個點是兩個點 i 與與 j 之間的距離，之間的距離，xij 0 或或 1（1表示連接

53、，表示連接，0 表示不連接），則有：表示不連接），則有：, 1, 1.min),(= = = ViijVjijAjiijijxxtsxd每個頂點只有一條邊出去每個頂點只有一條邊出去除起點和終點外，各邊不構成圈除起點和終點外，各邊不構成圈歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 每個頂點只有一條邊進入每個頂點只有一條邊進入例：例：圖圖 G 如所示，求如所示，求G的的最優(yōu)最優(yōu)HamiltonHamilton圈。圈。v1v7v2v3v4v6v5123465156432解：對頂點編號為解：對頂點編號為1到到7，找到各邊的權找到各邊的權 = =04100510022406110010031006051001

54、00100515063100100100100604100210010034012310010010010w決策變量為決策變量為0 ijx注：沒有的邊則取值注：沒有的邊則取值超過所有邊權之和，超過所有邊權之和，以頂點以頂點1 為起點。為起點。歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 求解程序為：求解程序為：!define sets;sets: cities/1.7/:level; !level(i)= the level of city; link(cities, cities): distance, !The distance matrix; x; ! x(i,j)=1 if we use li

55、nk i, j;endsets歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 !define datas;data: !Distance matrix, it need not be symmetirc; distance = 0 1 100 100 100 3 2 1 0 4 3 100 100 2 100 4 0 6 100 100 100 100 3 6 0 5 1 5 100 100 100 5 0 6 100 3 100 100 1 6 0 4 2 2 100 5 100 4 0 ;enddata歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 ! Minimize total distance of t

56、he links;min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j);n=size(cities); !The model size;!For city i;for(cities(i) :! It must be entered; sum(cities(j)| j #ne# i: x(j,i)=1;! It must be departed; sum(cities(j)| j #ne# i: x(i,j)=1; );歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 for(cities(i) :! level(j)=levle(i)+1, if we link

57、 j and i; for(cities(j)| j #gt# 1 #and# j #ne# i : level(j) = level(i) + x(i,j) - (n-2)*(1-x(i,j) + (n-3)*x(j,i); ); );! Make the xs 0/1;for(link : bin(x);! For the first and last stop;for(cities(i) | i #gt# 1 : level(i)=1+(n-2)*x(i,1); );歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 求解結果為：求解結果為：目標值為目標值為28解為：解為：X( 1, 7) 1.000

58、000X( 2, 1) 1.000000X( 3, 2) 1.000000X( 4, 3) 1.000000X( 5, 4) 1.000000X( 6, 5) 1.000000X( 7, 6) 1.000000v1v7v2v3v4v6v5123465156432歐拉圖和哈密爾頓圖歐拉圖和哈密爾頓圖 著色、匹配、平面圖著色、匹配、平面圖四色問題四色問題1840年數(shù)學家麥比烏斯（年數(shù)學家麥比烏斯（Mbius）提出一個猜想：）提出一個猜想：任何平面地圖，總可以把它的一個國家用四種顏色任何平面地圖，總可以把它的一個國家用四種顏色的一種著染，使相鄰國家著不同色。的一種著染，使相鄰國家著不同色。這就是著名

59、的這就是著名的四色猜想四色猜想。1890年希五德（年希五德（Heawood）指出指出“4換為換為5”猜想成立。猜想成立。1976年兩位數(shù)學家在三臺百年兩位數(shù)學家在三臺百萬次的電子計算機上花了萬次的電子計算機上花了1200小時證明了猜想成立。小時證明了猜想成立。猜想成為定理。猜想成為定理。映射映射設設A, B是兩個集合，是兩個集合，是是A到到B的一個映射，記為的一個映射，記為 ：AB，對，對記記特別地當特別地當 Bb 時，時，-1(B)也記為也記為 -1(b)。著色、匹配、平面圖著色、匹配、平面圖BBAA , )(|) ( | )() (1BxxBAaaA = = = = f ff ff ff

60、f定義：定義：給定圖給定圖G =(V,E),稱映射稱映射：E 1,2, k為為 G 的一個的一個k-邊著色邊著色，簡稱，簡稱邊著色邊著色，稱，稱 1,2, k 為為色集色集。若。若為為G 的邊著色且的邊著色且e,e E當當e 與與e相鄰相鄰時，時，(e) (e) ，則稱該著色是，則稱該著色是正常正常的。圖的。圖 G 的正的正常常 k-邊著色的最小邊著色的最小 k 值稱為值稱為 G 的的邊色數(shù)邊色數(shù)，記為，記為c (G), 簡記為簡記為c 。 若圖若圖 G 存在一個正常存在一個正常 k-邊著色，則稱邊著色，則稱 G 是是 k-邊可邊可著色的著色的。若若為圖為圖G 的邊著色，的邊著色，e為為G的邊