圖論講稿-wenkub
2023-02-08 12:54:13 本頁面
【正文】 ，其關聯(lián)矩陣 ,其中：2) 對有向圖 ，其關聯(lián)矩陣 ,其中：4) 圖的頂點度定義 1) 在無向圖 G中，與頂點 v關聯(lián)的邊的數目 (環(huán)算兩次 ),稱為頂點 v的 度 或 次數 ，記為 d(v)或 dG(v).稱度為奇數的頂點為 奇點 ，度為偶數的頂點為 偶點 .2) 在有向圖中，從頂點 v引出的邊的數目稱為頂點 v的 出度 ，記為 d+(v)，從頂點 v引入的邊的數目稱為 v的 入度 ，記為 d (v). 稱 d(v)= d+(v)+d (v)為頂點 v的 度 或 次數 ．定理的個數為偶數．推論 任何圖中奇點5) 路和連通 定義 1) 無向圖 G的一條 途徑 （或 通道 或 鏈 ）是指一個有限非空序列 ，它的項交替 地為頂點和邊，使得對 ， 的端點是 和 ,稱 W是從 到 的一條 途徑 ，或一條 途徑 . 整數 k稱為 W的 長 . 頂點 和 分別稱為的 起點 和 終點 ,而 稱為 W的 內部頂點 . 2) 若途徑 W的邊互不相同但頂點可重復，則稱 W為 跡 或 簡單鏈 . 3) 若途徑 W的頂點和邊均互不相同，則稱 W為 路或 路徑 . 一條起點為 ,終點為 的路稱為 路記為 定義 1) 途徑 中由相繼項構成子序列 稱為途徑 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．最短路問題及算法 最短路問題是圖論應用的基本問題，很多實際問題，如線路的布設、運輸安排、運輸網絡最小費用流等問題 ,都可通過建立最短路問題模型來求解 .?最短路的定義?最短路問題的兩種方法： Dijkstra（迪杰斯特拉）和 Floyd算法 .1) 求賦權圖中從給定點到其余頂點的最短路 .2) 求賦權圖中任意兩點間的最短路 . 2) 在賦權圖 G中，從頂點 u到頂點 v的具有最小權定義 1) 若 H是賦權圖 G的一個子圖，則稱 H的各邊的權和 為 H的 權 . 類似地，若稱為路 P的 權 ．若 P(u,v)是賦權圖 G中從 u到 v的路 ,稱 的路 P*(u,v)，稱為 u到 v的 最短路 ． 3) 把賦權圖 G中一條路的權稱為它的 長 ，把 (u,v)路的最小權稱為 u和 v之間的 距離 ，并記作 d(u,v). 1) 賦權圖中從給定點到其余頂點的最短路 假設 G為賦權有向圖或無向圖， G邊上的權均非負．若 ，則規(guī)定 最短路是一條路，且最短路的任一節(jié)也是最短路．求下面賦權圖中頂點 u0到其余頂點的最短路．Dijkstra算法 : 求 G中從頂點 u0到其余頂點的最短路 . 1) 置 ，對 ， ， 且 . 2) 對每個 ，用代替 ，計算 ，并把達到這個最小值的一個頂點記為 ，置 3) 若 ，則停止；若
教學課件相關推薦
鄂ICP備17016276號-1