圖論講稿-文庫吧資料
2025-01-24 12:54本頁面
【正文】 定義 圖 G的 階 是指圖的頂點(diǎn)數(shù) |V(G)|, 用 來表示；圖的邊的數(shù)目 |E(G)|用 來表示 . 也用 來表示邊是非空有限集，稱為 頂 點(diǎn)集 ，1)2) E(G)是頂點(diǎn)集 V(G)中的無序或有序的元素對表示圖， 簡記 用 定義 若一個圖的頂點(diǎn)集和邊集都是有限集，則稱 其為 有限圖 . 只有一個頂點(diǎn)的圖稱為 平凡圖 ，其他的 所有圖都稱為 非平凡圖 . 定義 若 圖 G中的邊均為有序偶對 ,稱 G為 有向邊 為 無向邊 ，稱 e連接 和 ，頂點(diǎn) 和 稱圖 . 稱邊 為 有向邊 或 弧 ,稱 是從連接 ，稱 為 e的弧 尾 ，稱 為 e的弧 頭 . 若圖 G中的邊均為無序偶對 ，稱 G為 無向圖 .稱為 e的 端點(diǎn) . 既有無向邊又有有向邊的圖稱為 混合圖 . 常用術(shù)語1) 邊和它的兩端點(diǎn)稱為互相 關(guān)聯(lián) .2)與同一條邊關(guān)聯(lián)的兩個端點(diǎn)稱為 相鄰 的頂點(diǎn)，與同一個頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱為 相鄰 的邊 . 3) 端點(diǎn)重合為一點(diǎn)的邊稱為 環(huán) ， 端點(diǎn)不相同的邊稱為 連桿 .4) 若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為 重邊 ．5) 既沒有環(huán)也沒有重邊的圖，稱為 簡單圖 ． 常用術(shù)語6) 任意兩頂點(diǎn)都相鄰的簡單圖 ,稱為完全圖 . 記為 Kv. 7) 若 ， ， 且 X 中任意兩頂點(diǎn)不， 相鄰， Y 中任意兩頂點(diǎn)不相鄰，則稱為 二部圖 或 偶圖 ；若 X中每一頂點(diǎn)皆與 Y 中一切頂點(diǎn)相鄰 ,稱為完全二部圖 或 完全偶圖 ,記為 (m=|X|,n=|Y|)．8) 圖 叫做 星 .二部圖2) 賦權(quán)圖與子圖 定義 若圖 的每一條邊 e 都賦以一個實(shí)數(shù) w(e)，稱 w(e)為邊 e的 權(quán) ， G 連同邊上的權(quán)稱為 賦權(quán)圖 . 定義 設(shè) 和 是兩個圖 . 1) 若 ,稱 是 的一個 子圖 ,記 2) 若 ， ，則稱 是 的 生成子圖 . 3) 若 ，且 ，以 為頂點(diǎn)集，以兩端點(diǎn) 均在 中的邊的全體為邊集的圖 的子圖，稱 4) 若 ，且 ，以 為邊集，以 的端點(diǎn) 集為頂點(diǎn)集的圖 的子圖，稱為 的 由 導(dǎo)出的 邊導(dǎo)出的子圖 ，記為 . 為 的 由 導(dǎo)出的子圖 ，記為 .3) 圖的矩陣表示 鄰接矩陣 :1) 對無向圖 ，其鄰接矩陣 ，其中： (以下均假設(shè)圖為簡單圖 ).2) 對有向圖 ,其鄰接矩陣 ,其中： 其中：3) 對有向賦權(quán)圖 , 其鄰接矩陣 ,對于無向賦權(quán)圖的鄰接矩陣可類似定義 . 關(guān)聯(lián)矩陣 1) 對無向圖 ，其關(guān)聯(lián)矩陣 ,其中：2) 對有向圖 ，其關(guān)聯(lián)矩陣 ,其中：4) 圖的頂點(diǎn)度定義 1) 在無向圖 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ù) ．定理的個數(shù)為偶數(shù)．推論 任何圖中奇點(diǎn)5) 路和連通 定義 1) 無向圖 G的一條 途徑 （或 通道 或 鏈 ）是指一個有限非空序列 ，它的項(xiàng)交替
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1