圖論講稿(已修改)
2025-01-28 12:54 本頁(yè)面
【正文】 圖論在建模中的應(yīng)用下回停 1. 圖論的基本概念2. 最短路問題及算法 圖論模型基礎(chǔ)知識(shí)3. 最小生成樹問題及算法 4. 哈密爾頓圖5. 歐拉圖1) 圖的概念2) 賦權(quán)圖與子圖3) 圖的矩陣表示4) 圖的頂點(diǎn)度5) 路和連通1) 圖的概念 定義 一個(gè) 圖 G是指一個(gè)二元組 (V(G),E(G))，其中 : 其中元素稱為圖 G的 頂點(diǎn) .組成的集合，即稱為 邊集 ,其中元素稱為 邊 . 定義 圖 G的 階 是指圖的頂點(diǎn)數(shù) |V(G)|, 用 來(lái)表示；圖的邊的數(shù)目 |E(G)|用 來(lái)表示 . 也用 來(lái)表示邊是非空有限集，稱為 頂 點(diǎn)集 ，1)2) E(G)是頂點(diǎn)集 V(G)中的無(wú)序或有序的元素對(duì)表示圖， 簡(jiǎn)記 用 定義 若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱 其為 有限圖 . 只有一個(gè)頂點(diǎn)的圖稱為 平凡圖 ，其他的 所有圖都稱為 非平凡圖 . 定義 若 圖 G中的邊均為有序偶對(duì) ,稱 G為 有向邊 為 無(wú)向邊 ，稱 e連接 和 ，頂點(diǎn) 和 稱圖 . 稱邊 為 有向邊 或 弧 ,稱 是從連接 ，稱 為 e的弧 尾 ，稱 為 e的弧 頭 . 若圖 G中的邊均為無(wú)序偶對(duì) ，稱 G為 無(wú)向圖 .稱為 e的 端點(diǎn) . 既有無(wú)向邊又有有向邊的圖稱為 混合圖 . 常用術(shù)語(yǔ)1) 邊和它的兩端點(diǎn)稱為互相 關(guān)聯(lián) .2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱為 相鄰 的頂點(diǎn)，與同一個(gè)頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱為 相鄰 的邊 . 3) 端點(diǎn)重合為一點(diǎn)的邊稱為 環(huán) ， 端點(diǎn)不相同的邊稱為 連桿 .4) 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為 重邊 ．5) 既沒有環(huán)也沒有重邊的圖，稱為 簡(jiǎn)單圖 ． 常用術(shù)語(yǔ)6) 任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖 ,稱為完全圖 . 記為 Kv. 7) 若 ， ， 且 X 中任意兩頂點(diǎn)不， 相鄰， Y 中任意兩頂點(diǎn)不相鄰，則稱為 二部圖 或 偶圖 ；若 X中每一頂點(diǎn)皆與 Y 中一切頂點(diǎn)相鄰 ,稱為完全二部圖 或 完全偶圖 ,記為 (m=|X|,n=|Y|)．8) 圖 叫做 星 .二部圖2) 賦權(quán)圖與子圖 定義 若圖 的每一條邊 e 都賦以一個(gè)實(shí)數(shù) w(e)，稱 w(e)為邊 e的 權(quán) ， G 連同邊上的權(quán)稱為 賦權(quán)圖 . 定義 設(shè) 和 是兩個(gè)圖 . 1) 若 ,稱 是 的一個(gè) 子圖 ,記 2) 若 ， ，則稱 是 的 生成子圖 . 3) 若 ，且 ，以 為頂點(diǎn)集，以兩端點(diǎn) 均在 中的邊的全體為邊集的圖 的子圖，稱 4) 若 ，且 ，以 為邊集，以 的端點(diǎn) 集為頂點(diǎn)集的圖 的子圖，稱為 的 由 導(dǎo)出的 邊導(dǎo)出的子圖 ，記為 . 為 的 由 導(dǎo)出的子圖 ，記為 .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).
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1