《可視化計(jì)算》第7章圖論基礎(chǔ)與應(yīng)用(B)

第7章圖論根底與應(yīng)用

PARTB《可視化計(jì)算》1圖算法的應(yīng)用最小生成樹-與網(wǎng)絡(luò)建設(shè)本錢Dijkstra算法-尋找網(wǎng)絡(luò)中的最短路徑獨(dú)立集-四色定理支配集-商業(yè)網(wǎng)點(diǎn)的布局2假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，那么連通n個(gè)城市只需要n-1條線路。這時(shí)，自然會(huì)考慮這樣一個(gè)問題，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通信網(wǎng)在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價(jià)。n個(gè)城市之間，最多可能設(shè)置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，以使總的消耗最少呢?網(wǎng)絡(luò)建設(shè)本錢與最小生成樹3對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一生成樹都可以是一個(gè)網(wǎng)絡(luò)現(xiàn)在，我們要選擇這樣一棵生成樹，也就是使總的消耗最少這個(gè)問題就是構(gòu)造連通網(wǎng)的最小生成樹(MinimumSpanningTree,MST)的問題。一棵生成樹的代價(jià)就是樹上各邊的代價(jià)之和最小生成樹4最小生成樹(MST)性質(zhì)：假設(shè)G=(V，E)是一個(gè)連通圖，U是頂點(diǎn)集V的一個(gè)非空子集。假設(shè)(u，v)是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U，那么必存在一棵包含邊(u，v)的最小生成樹最小生成樹5最小生成樹算法Prim算法：假設(shè)G=(V，E)是連通圖，TE是N上最小生成樹中邊的集合算法從U={u0}(u0∈V)，TE={}開始，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊(u，v)∈E中找一條代價(jià)最小的邊(u0，v0)并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，那么T=(V,TE)為圖G的最小生成樹6最小生成樹算法：Prim算法例子v6v5v3v2v4v1v6v5v3v4v2v1(c)(b)(a)5v6v5v3v4v2v1651536642v6v5v3v4v2v1v6v5v3v2v4v1v6v5v3v2v4v1(d)(e)(f)Prim算法構(gòu)造最小生成樹的過程7Prim算法思想：任意時(shí)刻的中間結(jié)果都是一棵樹從一個(gè)點(diǎn)開始，每次都花最少的代價(jià)，用一條邊把一個(gè)不在樹里的點(diǎn)加進(jìn)來算法復(fù)雜度：每次選邊的復(fù)雜度為O(logm)，所以時(shí)間復(fù)雜度為O(m+nlogm)最小生成樹算法：Prim算法8用RAPTOR實(shí)現(xiàn)Prim算法Prim子程序9用RAPTOR實(shí)現(xiàn)Prim算法init子圖10用RAPTOR實(shí)現(xiàn)Prim算法Fun1子圖11用RAPTOR實(shí)現(xiàn)Prim算法Fun2子圖12Prim算法的計(jì)算結(jié)果v6v5v3v2v4v15v6v5v3v4v2v165153664213網(wǎng)絡(luò)中的最短路徑如果圖中從一個(gè)頂點(diǎn)可以到達(dá)另一個(gè)頂點(diǎn)，那么稱這兩個(gè)頂點(diǎn)間存在一條路徑從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)間可能存在多條路徑，而每條路徑上經(jīng)過的邊數(shù)并不一定相同對(duì)網(wǎng)絡(luò)而言，那么路徑長(zhǎng)度為路徑上各邊的權(quán)值的總和，兩個(gè)頂點(diǎn)間路徑長(zhǎng)度最短的那條路徑稱為兩個(gè)頂點(diǎn)間的最短路徑，其路徑長(zhǎng)度稱為最短路徑長(zhǎng)度14尋找網(wǎng)絡(luò)中的最短路徑-

Dijkstra算法SingleSource/AllDestinations15Dijkstra算法根本思路設(shè)置一個(gè)集合S，存放已求出最短路徑的頂點(diǎn)，V-S是尚未確定最短路徑的頂點(diǎn)集合每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值，集合S中頂點(diǎn)的距離值是從頂點(diǎn)v1到該頂點(diǎn)的最短路徑長(zhǎng)度；集合V-S中頂點(diǎn)的距離值是從頂點(diǎn)v1到該頂點(diǎn)的只包括集合S中頂點(diǎn)為中間頂點(diǎn)的最短路徑長(zhǎng)度16初始狀態(tài)集合S中只有頂點(diǎn)v1，頂點(diǎn)v1對(duì)應(yīng)的距離值為0；集合V-S中頂點(diǎn)vi的距離值為邊(v1,vi)(i=2,…,n)的權(quán)；如果v1和vi間無邊直接相連，那么vi的距離值為∞17處理原那么〔1〕在集合V-S中選擇距離值最小的頂點(diǎn)vmin參加集合S；〔2〕對(duì)集合V-S中各頂點(diǎn)的距離值進(jìn)行修正：如果參加頂點(diǎn)vmin為中間頂點(diǎn)后，使v1到vi的距離值比原來的距離值更小，那么修改vi的距離值；〔3〕重復(fù)〔1〕、〔2〕操作，直到從v1出發(fā)可以到達(dá)的所有頂點(diǎn)都在集合S中為止。18Dijkstra算法19Dijkstra算法Init子圖20Dijkstra算法Path子圖21Dijkstra算法choose子程序22Dijkstra算法Input_output子圖23Dijkstra算法的結(jié)果輸出24四色定理-獨(dú)立集25圖的著色兩類著色問題問題：1．給定無環(huán)圖G=(V,E)，用m種顏色為圖中的每條邊著色，要求每條邊著一種顏色，并使相鄰兩條邊有著不同的顏色，這個(gè)問題稱為圖的邊著色問題。2．給定無向圖G=(V,E)，用m種顏色為圖中的每個(gè)頂點(diǎn)著色，要求每個(gè)頂點(diǎn)著一種顏色，并使相鄰兩頂點(diǎn)之間有著不同的顏色，這個(gè)問題稱為圖的頂著色問題26地圖的抽象27頂點(diǎn)著色－根本概念獨(dú)立集：對(duì)圖G=(V,E)，設(shè)S是V的一個(gè)子集，假設(shè)中任意兩個(gè)頂點(diǎn)在G中均不相鄰，那么稱S為G的一個(gè)獨(dú)立集。最大獨(dú)立集：如果G不包含適合|S'|＞|S|的獨(dú)立集S'，那么稱S為G的最大獨(dú)立集。極大覆蓋：設(shè)K是G的一個(gè)獨(dú)立集，并且對(duì)于V-K的任一頂點(diǎn)v，K+v都不是G的獨(dú)立集，那么稱K是G的一個(gè)極大覆蓋。極小覆蓋：極大獨(dú)立集的補(bǔ)集稱為極小覆蓋。V的子集K是G的極小覆蓋當(dāng)且僅當(dāng)：對(duì)于每個(gè)頂點(diǎn)v或者v屬于K，或者v的所有鄰點(diǎn)屬于K〔但兩者不同時(shí)成立〕。28頂點(diǎn)著色－根本概念K可著色：G的一個(gè)k頂點(diǎn)著色是指k種顏色1,2,…,k對(duì)于G各頂點(diǎn)的一個(gè)分配，如果任意兩個(gè)相鄰頂點(diǎn)都分配到不同的顏色，那么稱著色是正常的G的色數(shù)X〔G〕是指G為k可著色的k的最小值，假設(shè)X〔G〕=k，那么稱G是k色的29求頂色數(shù)的算法設(shè)計(jì)由“每個(gè)同色頂點(diǎn)集合中的兩兩頂點(diǎn)不相鄰”可以看出，同色頂點(diǎn)集實(shí)際上是一個(gè)獨(dú)立集用第1種顏色上色時(shí)，為了盡可能擴(kuò)大顏色1的頂點(diǎn)個(gè)數(shù)，逼近所用顏色數(shù)最少的目的事實(shí)上就是找出圖G的一個(gè)極大獨(dú)立集并給它涂上顏色1。用第2種顏色上色時(shí)，同樣選擇另一個(gè)極大獨(dú)立集涂色，...當(dāng)所有頂點(diǎn)涂色完畢，所用的顏色數(shù)即為所選的極大獨(dú)立集的個(gè)數(shù)。30算法步驟Step1：求G圖的所有極大獨(dú)立集Step2：求出一切假設(shè)干極大獨(dú)立集的和含所有頂點(diǎn)的子集；Step3：從中挑選所用極大獨(dú)立集個(gè)數(shù)最小值，即為X〔G〕31WelchPowell著色法

I．將圖G中的結(jié)點(diǎn)按度數(shù)的遞減順序進(jìn)行排列(這種排列可能不是唯一的，因?yàn)橛行┙Y(jié)點(diǎn)的度數(shù)相同)；II．用第一種顏色對(duì)第一結(jié)點(diǎn)著色，并按排列順序?qū)εc前面著色結(jié)點(diǎn)不鄰接的每一結(jié)點(diǎn)著上同樣的顏色；III．用第二種顏色對(duì)尚未著色的結(jié)點(diǎn)重復(fù)II，用第三種顏色繼續(xù)這種做法，直到所有的結(jié)點(diǎn)全部著上色為止。32WelchPowell著色法

給定圖G，用WelchPowell法對(duì)圖G著色33WelchPowell著色法

1、將圖G中的結(jié)點(diǎn)按度數(shù)的遞減順序排列：2、用第一種顏色對(duì)A5著第一種顏色，并對(duì)與A5不鄰接的結(jié)點(diǎn)A1也著第一種顏色。3、對(duì)結(jié)點(diǎn)A3及與A3不鄰接的結(jié)點(diǎn)A4、A8著第二種顏色。4、對(duì)結(jié)點(diǎn)A7及與A7不鄰接的結(jié)點(diǎn)A2、A6著第三種顏色。因此，圖G是三色的；但圖G不可能是二色的，因?yàn)锳1,A2,A3相互鄰接，故必須著三種顏色。所以x(G)=3。34地圖著色Main子圖35地圖著色Color_seq子圖36地圖著色Countedges子圖37地圖著色setColor子圖38地圖著色Lookformaxedges子程序39地圖著色結(jié)果40商業(yè)網(wǎng)點(diǎn)的布局一個(gè)小城，要設(shè)置水井，假設(shè)所有人都住在頂點(diǎn)所在的位置問題：如何配置，使得居民只要走過一條街，就可以到達(dá)水井，并且水井的數(shù)量最小41課堂提問所有的居民住在街口走最多一個(gè)街道的距離至少要幾輛售貨車42可抽象的概念圖：無向圖邊：表示街道節(jié)點(diǎn)：表示路口問題：求最少的冰激凌車的配置43生活中的同類問題安置郵筒消防站城市中配置教育資源在一個(gè)國(guó)家配置航空、鐵路樞紐這些問題容易求解嗎？如何解？44開始時(shí)的思考：考慮所有的放置冰激凌銷售車的可能情況，然后檢驗(yàn)?zāi)姆N是最好的在這城鎮(zhèn)的26個(gè)街角中，如果放置一臺(tái)銷售車有26種放置方法很容易檢驗(yàn)這26種放置方法很明顯沒有一種滿足要求〔明顯不夠〕45開始時(shí)的思考-：如果有兩輛銷售車那么有26個(gè)地方可以放置第一輛車這樣一來，除掉放置第一輛車的地方，還有25個(gè)地方來放置第二輛〔不會(huì)在一個(gè)地方放兩輛車〕將有26*25種可能性要檢驗(yàn)事實(shí)上，只需要檢驗(yàn)其中的一半〔325〕因?yàn)檫@兩輛車中的哪一輛放置在一個(gè)地方是無關(guān)緊要的46開始時(shí)的思考--：三輛車可能的情況？26×25×24/6=2600四輛車可能的情況？26×25×24×23/24=14950…總共的實(shí)驗(yàn)次數(shù)？226，也就是67108864〔六千七百萬〕1秒鐘檢驗(yàn)一個(gè)方案大約需要777天47最小支配集問題冰激凌銷售車問題正式地被稱為“最小支配集”問題支配集〔Dominationset〕可描述如下：給定無向圖G=〈V,E〉，其中V是大小為n的點(diǎn)集，E是邊集那么V的一個(gè)子集S稱為支配集當(dāng)且僅當(dāng)對(duì)于V-S中任何一個(gè)點(diǎn)v，都有S中的某個(gè)定點(diǎn)u,使得(u,v)∈E這時(shí)稱點(diǎn)u支配點(diǎn)v，并把S中的點(diǎn)稱為支配點(diǎn)支配集的判定問題就是判定圖G中是否有大小不大于正整數(shù)k〔k<=n〕的支配集其優(yōu)化問題就是求出規(guī)模最小的支配集48使用RAPTOR求解支配集問題程1、建立鄰接矩陣2、選擇算法3、進(jìn)行計(jì)算和分析4、進(jìn)行比較49根本解法對(duì)有N個(gè)結(jié)點(diǎn)的旅行城鎮(zhèn)問題，給N個(gè)路口編號(hào)，1,…,N50最初的求解方法蠻力法〔brutr-force〕、窮舉法檢驗(yàn)所有的可能性，找出滿足條件的解理論計(jì)算時(shí)間36個(gè)交叉點(diǎn)2000年46個(gè)交叉點(diǎn)2百萬年51貪心算法把第一輛銷售車放在連接最多街道數(shù)目的交叉點(diǎn)處第二輛放在下一個(gè)類似的交叉點(diǎn)處如此類推但是