圖論講稿(存儲版)
【正文】 .3) 圖的矩陣表示 鄰接矩陣 :1) 對無向圖 ，其鄰接矩陣 ，其中： (以下均假設(shè)圖為簡單圖 ).2) 對有向圖 ,其鄰接矩陣 ,其中： 其中：3) 對有向賦權(quán)圖 , 其鄰接矩陣 ,對于無向賦權(quán)圖的鄰接矩陣可類似定義 . 關(guān)聯(lián)矩陣 1) 對無向圖 ，其關(guān)聯(lián)矩陣 ,其中：2) 對有向圖 ，其關(guān)聯(lián)矩陣 ,其中：4) 圖的頂點度定義 1) 在無向圖 G中，與頂點 v關(guān)聯(lián)的邊的數(shù)目 (環(huán)算兩次 ),稱為頂點 v的 度 或 次數(shù) ，記為 d(v)或 dG(v).稱度為奇數(shù)的頂點為 奇點 ，度為偶數(shù)的頂點為 偶點 .2) 在有向圖中，從頂點 v引出的邊的數(shù)目稱為頂點 v的 出度 ，記為 d+(v)，從頂點 v引入的邊的數(shù)目稱為 v的 入度 ，記為 d (v). 稱 d(v)= d+(v)+d (v)為頂點 v的 度 或 次數(shù) ．定理的個數(shù)為偶數(shù)．推論 任何圖中奇點5) 路和連通 定義 1) 無向圖 G的一條 途徑 （或 通道 或 鏈 ）是指一個有限非空序列 ，它的項交替 地為頂點和邊，使得對 ， 的端點是 和 ,稱 W是從 到 的一條 途徑 ，或一條 途徑 . 整數(shù) k稱為 W的 長 . 頂點 和 分別稱為的 起點 和 終點 ,而 稱為 W的 內(nèi)部頂點 . 2) 若途徑 W的邊互不相同但頂點可重復(fù)，則稱 W為 跡 或 簡單鏈 . 3) 若途徑 W的頂點和邊均互不相同，則稱 W為 路或 路徑 . 一條起點為 ,終點為 的路稱為 路記為 定義 1) 途徑 中由相繼項構(gòu)成子序列 稱為途徑 W的 節(jié) . 2) 起點與終點重合的途徑稱為 閉途徑 . 3) 起點與終點重合的的路稱為 圈 (或 回路 )，長為 k的圈稱為 k階圈 ，記為 Ck. 4) 若在圖 G中存在 (u,v)路，則稱頂點 u和 v在圖 G中 連通 . 5) 若在圖 G中頂點 u和 v是連通的，則頂點 u和 v之之間的 距離 d(u,v)是指圖 G中最短 (u,v)路的長；若沒沒有路連接 u和 v，則定義為無窮大 . 6) 圖 G中任意兩點皆連通的圖稱為 連通圖 ． 7) 對于有向圖 G，若 ，且 有 類似地，可定義 有向跡 ， 有向路 和 有向圈 .頭 和尾 ，則稱 W為 有向途徑 . 例 在右圖中： 途徑或鏈： 跡或簡單鏈： 路或路徑： 圈或回路：2．最短路問題及算法 最短路問題是圖論應(yīng)用的基本問題，很多實際問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用流等問題 ,都可通過建立最短路問題模型來求解 .?最短路的定義?最短路問題的兩種方法： Dijkstra（迪杰斯特拉）和 Floyd算法 .1) 求賦權(quán)圖中從給定點到其余頂點的最短路 .2) 求賦權(quán)圖中任意兩點間的最短路 . 2) 在賦權(quán)圖 G中，從頂點 u到頂點 v的具有最小權(quán)定義 1) 若 H是賦權(quán)圖 G的一個子圖，則稱 H的各邊的權(quán)和 為 H的 權(quán) . 類似地，若稱為路 P的 權(quán) ．若 P(u,v)是賦權(quán)圖 G中從 u到 v的路 ,稱 的路 P*(u,v)，稱為 u到 v的 最短路 ． 3) 把賦權(quán)圖 G中一條路的權(quán)稱為它的 長 ，把 (u,v)路的最小權(quán)稱為 u和 v之間的 距離 ，并記作 d(u,v). 1) 賦權(quán)圖中從給定點到其余頂點的最短路 假設(shè) G為賦權(quán)有向圖或無向圖， G邊上的權(quán)均非負．若 ，則規(guī)定 最短路是一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1