尤拉与汉米尔顿路径.ppt

第八章 圖形 8.1 圖形和圖學模型 定義：圖形(graph)G = (V, E)是由頂點(vertex)（或稱結點node）的非空集合V，以及邊(edge)的集合E所構成。每一個邊都相關於一個或兩個頂點，稱為這個邊的端點(endpoint)。而我們稱此邊連通它的端點。 定義：方向圖(directed graph or digraph)(V, E)是由一個頂點組成之非空集合V和有向邊(directed edges或arcs)的集合E所形成。每一個有方向之邊(u, v)相關於一對有序的頂點，始於u而終於v。 三個主要的問題能幫助我們了解圖形之結構： 圖形中的邊有無方向性？ 如果圖形是無方向性的，那是否會有重邊出現？同樣的，若是個有向圖，圖中是否會出現多重有向邊？ 圖中是否會產生迴圈？ 圖學模型 例：生態學中的食物鏈 圖形被用於表現生物界中不同物種間之互動。例如，生態學中各種動物間的競爭關係，能以食物鏈圖形來表現。每個頂點代表一個物種；兩頂點間的無向邊，代表這兩個物種間存在著競爭（也就是說，牠們的食物來源會重疊）。食物鏈圖是個簡單圖，沒有迴圈，也沒有重邊。右圖表現的是森林中的生態。從圖中，可以發現松鼠和負鼠間有競爭關係，而烏鴉和地鼠間則無。 例：社交關係圖 我們能用圖形來表現兩人是否相識。社群中的每個個人都為一個頂點；兩頂點間若連接著無向邊，代表這兩個人互相認識對方。圖形中不會出現重邊，通常也沒有迴圈（除非我們希望包括自我認識）。下圖表現出一個小型的社交圖。 例：影響關係圖 在研究群體行為時發現特定人士能影響其他人的想法。一個稱為影響關係圖的有向圖，能用來顯示這種行為的模式。團體中的個人都是個頂點。一個有向邊從頂點a指向頂點b，表示個人a將對個人b產生影響。這種圖形不會包含迴圈，也不會有重邊。右圖即為某團體之影響關係圖。在這個團體中，黛博拉會影響布萊恩、福瑞德和琳達。但是沒有人能影響她。此外，我們也發現伊凡與布萊恩間會互相影響。 例：好萊塢圖 在好萊塢圖中，頂點代表的是演員，兩個演員曾經合作演出同一齣電影時，便在這兩個頂點間聯結一個邊。很明顯的，這個圖是個簡單圖，因為它沒有方向、沒有重邊，也不會有迴圈。根據網際網路電影資料庫(the Internet Movie Database)，在2006年一月時，好萊塢圖包含了637,099個演員，他們出現在339,896齣電影中。而圖中邊的數目超過了兩千萬。稍後，我們將再度討論好萊塢圖中的某些面向。 例：循環賽圖 在賽程中，任意兩個參賽隊伍都將對壘一次的方式稱為循環賽。這種賽程的結果可以用圖形來表示。每個頂點代表一個參賽隊伍，(a, b)這個有向邊表示a隊打敗了b隊。這類圖形是個簡單方向圖，沒有迴圈與重邊（因為沒有兩隊對壘超過一次）。右圖所表現的就是這種方向圖。我們可以觀察到隊伍１在整個賽程中是全勝的，而隊伍３則完全沒贏過。 例：合作關係圖 合作關係圖是用來表現學術論文中共同作者的關係圖。圖中的頂點代表的是人（也許能將之局限於某個學術領域的社群），而邊所聯結的兩個人，表示他們曾經合作過論文。這種圖是個簡單圖，沒有方向，也沒有迴圈與重邊。在數學研究領域中所形成的合作關係圖包含了超過400,000個頂點和675,000個邊。 例：電話通話圖 圖形也能建構電話通話記錄的網路模型。以電話號碼為頂點，當由某個號碼打給另一個號碼時，便產生一條聯結這兩個頂點的有向邊。這樣一來，就產生了一個含多重有向邊的方向圖。 下圖(a)是個包含七個電話號碼的小型電話通路圖。。當我們只關心兩個號碼間是否曾經通過話時，便能將圖形轉換成沒有方向的圖，如圖(b)。 例：循序圖 當某些電腦語句能平行處理時，電腦程式的執行便能更加快速。但是，此時便須注意某些需要其他語句執行後所得結果的語句。這些電腦語句間的依賴關係可以用方向圖來展現。每一個語句是一個頂點，若一個有向邊的始點尚未執行，則其終點的頂點（語句）將無法執行。這類的圖形，如右圖，稱為循序圖(Precedence graph)。圖中可以看出當S1，S2與S4尚未執行時，S5將無法被執行。 8.2 圖學術語和特殊形態的圖形 定義：在無向圖G中，稱兩頂點u與v鄰接(adjacent or neighbors)。若這兩個頂點為同一個邊的兩個端點。若e相關於{u,v}，則稱邊e接合著(incident with)頂點u與頂點v；或是邊e連通(connect) u與v。而頂點u與v稱為相關於{u,v}之邊的端點(endpoints)。 定義：一個無向圖之頂點的分支度(degree)為接合著此頂點之邊的數目，但是一個迴圈則提供此頂點兩個分支度。頂點v的分支度記為deg(v)。 一個頂點的分支度為0時稱為孤立的(isolated)；一個頂點稱為垂懸的(pen