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