1、人工智能人工智能數學基礎數學基礎項翔開課吧人工智能學院2020.02第五節課 圖論 圖的由來 圖的構成 圖的表示 鄰接矩陣 圖的種類 最短路徑問題 Dijkstra算法 樹 最小生成樹 圖與人工智能圖的由來對現實世界的抽象哥尼斯堡七橋問題圖的由來對現實世界的抽象化學研究中的分子結構表示如， 丁烷（C4H10）的兩種同分異構結構用圖可以表示為：hhhhhhhhhhhhhhhhhhhh圖的由來對現實世界的抽象高鐵線路圖圖的由來對現實世界的抽象期末考試時間的排布一個學校要對期末考試進行排布，如何避免時間上的沖突？抽象為圖的模型來解決，則頂點代表待排布的課程，連接兩個頂點邊表示有學生同時選擇了這兩門課

2、程。問題轉化為用不同的顏色去給頂點上色（頂點著色問；四色問題），要求不同時間段的考試（頂點）用不同的顏色，相同時間段的考試（頂點）用相同的顏色abcefd圖的構成什么構成了圖：- 頂點和邊構成的網絡結構圖的構成我們關心什么？- 圖中有多少個點- 哪些點之間有線（邊）連接我們不關心什么？- 邊的長度- 邊是否彎曲- 點的絕對位置ACDB圖的構成文字定義： 一個圖是一個序偶，符號表示為： G = V = v1, v2, , vn為有限非空集合，Vi稱為頂點，或簡稱點，V稱為頂點集，用|V|表示頂點數 E是有限集合，為一個圖的所有邊的集合，稱為邊集，且E中的每個元素都有V中的結點對與之對應，用|E|

3、表示邊數圖的構成常見圖的名詞解釋：有限圖：頂點數和邊數都有限的圖空圖：邊集為空（無邊）的圖平凡圖：只有一個頂點的圖n階圖：頂點數為n的圖(n, m)圖：頂點數為n，邊數為m的圖環：端點重合為一點的邊重邊：連接兩個相同頂點的多條邊（大于1條），邊的條數稱作邊的重數簡單圖：圖中沒有環且沒有重邊復合圖：圖中有環或者有重邊或者二者均有v1v2v3v4e1e2e3e4e5e6圖的表示 集合表示：- 對于一個圖，將其記為G=,并寫出V和E的集合表示 圖形表示：- 用小圓圈表示V中的結點- 有序的結點對表示由結點u指向結點v的有向邊e- 此時u稱為e的始點，v稱為e的終點，統稱為e的端點- 無序的節點對(u

4、, v)（或(v, u)）表示結點u和結點v之間的無向邊- 此時僅稱u，v為邊e的兩個端點圖的表示例：設圖G=，且V=v1, v2, v3, v4, v5， E = e1, e2, e3, e4, e5, e6，且圖中的邊為：e1 = (v1, v2)，e2 = ，e3 = (v1, v4)，e4 = (v2, v3)，e5 = ，e6 = (v3, v3)請畫出圖G的圖形表示，并說明哪些邊是有向邊，哪些邊是無向邊。圖的表示解：G的圖形表示為：其中， e1、e3、e4、e6是無向邊，e2、e5是有向邊。 v v3 3e e1 1e e2 2e e3 3e e5 5v v2 2v v1 1v v

5、4 4e e4 4v v5 5e e6 6圖的表示例：圖G=的圖形表示如下所示，請寫出相應的G的集合表示。1 12 23 34 45 5圖的表示解：G= = 1, 2, 3, 4, 5，(1, 4)，(1, 5)，(2, 3)，1 12 23 34 45 5圖的表示集合表示：- Pros：可以精確描述圖的組成信息- Cons：較為抽象，不易于直觀理解圖形表示：- Pros：可以直觀形象地表示圖，易于理解- Cons：當圖中結點以及邊的數量比較大時，很難全部繪制出來圖的表示圖形表示，集合表示平分天下？No，實乃三國爭霸還有一種：矩陣表示Why？我們經常需要計算機幫助我們去處理圖的數據，然而對于計

6、算機而言，集合的形式或者圖形的形式都不太適合，而矩陣卻是非常適合計算機計算的形式。 011101101001110100101110000101110010AG鄰接矩陣鄰接矩陣例：寫出圖G的鄰接矩陣解：按照頂點的標號次序，各點相互之間的連接情況為：v v1 1v v2 2v v5 5v v4 4v v3 3v v6 6 0 0 1 1 1 1 1 1 0 01 11 1 0 0 1 1 0 0 0 01 11 1 1 1 0 0 1 1 0 00 01 1 0 0 1 1 1 1 1 10 00 0 0 0 0 0 1 1 0 01 11 1 1 1 0 0 0 0 1 1 0 0v vv v

7、v vv vv vv vv vv vv vv vv vv v6 65 54 43 32 21 16 65 54 43 32 21 1 011101101001110100101110000101110010AG鄰接矩陣圖的鄰接矩陣是唯一的嗎？ 一般而言，同一個圖按照不同的頂點排列次序，寫出的鄰接矩陣形式上是不同的，但是相互之間可以通過調換某些行或列的位置而得到。 對鄰接矩陣的行或列進行交換，對應的實際上是在對頂點的排序中調換頂點的位置 若不考慮頂點排序的不同產生的鄰接矩陣的不同，則圖與鄰接矩陣之間是一一對應的 實際操作上，往往略去頂點排序不同導致的鄰接矩陣的多樣性，選擇任意一種頂點次序得出的鄰

8、接矩陣作為該圖的鄰接矩陣圖的種類按邊有無方向分類：有向圖&無向圖&混合圖1 12 23 34 45 5圖的種類在混合圖中，將無向邊轉換為方向相反的兩條有向邊來處理：v v3 3v v2 2v v1 1v v3 3v v2 2v v1 1圖的種類按有無平行邊（重邊）分類：多重圖：有平行邊的圖線圖：無平行邊的圖簡單圖：無環的線圖a ab bc c1 12 23 33 31 14 42 2圖的種類按邊或頂點是否賦予權重分類：賦權圖&無權圖賦權圖： G是一個三重組或四重組，其中V是結點集合，E是邊的集合，f是從V到非負實數集合的函數，g是從E到非負實數集合的函數。圖的種類例：請

9、寫出此賦權圖中相應的函數。解：f2(a)=9，f2(b)=6，f2(c)=7，f2(d)=10；g2(a, b)=50，g2(a, c)=70，g2(a, d)=45，g2(b, d)=40，g2(c, d)=35， 10106 69 9c c7 7a ab bd d50504040707035354545圖的種類前述的分類方法彼此之間并非孤立的，往往綜合應用，比如前述的賦權圖：全稱為：無向賦權簡單圖10106 69 9c c7 7a ab bd d50504040707035354545最短路徑問題給出一個賦權圖，若頂點代表了不同的城市，權重代表了不同城市間的距離，給定起點，如何求出其到任意

10、一點的最短路徑？Dijkstra算法思路：把頂點集合V分成兩組： S：已解決的頂點的集合（初始時只含有源點V0） U：尚未確定的頂點集合將U中頂點按遞增的次序加入到S中，保證： 從源點V0到S中其他各頂點的長度都不大于從V0到U中任何頂點的最短路徑長度 每個頂點對應一個距離值S中頂點：從V0到此頂點的長度U中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度Dijkstra算法Dijkstra算法Dijkstra算法Dijkstra算法Dijkstra算法Dijkstra算法動圖演示：Dijkstra算法不適用的情況：- 權重為負c ca ab bd d10104040-70-7035354545樹定義：不含圈的連通圖生成樹性質：- 包含連通圖中所有的頂點的樹- 任意兩個連通的頂點之間有且僅有一條邊- 頂點數-邊數=1最小生成樹性質：- 僅針對賦權圖而言- “最小”指的是樹種所有邊的權重之和最小- 為“最小權重生成樹”的簡稱應用：- 不同城市間怎樣修路使得各個城市都能連接上又令總里程最短- 通信線路的鋪設最小生成樹如何得到？Kruskal算法：1. 構造一個只含原圖G中所有頂點，而不包含任何邊的子圖T2. 將圖中的邊按照權重大小進行從小到大的排序，形成集