圖論講稿-免費(fèi)閱讀
【正文】 選址問題 重心問題3．最小生成樹及算法1) 樹的定義與樹的特征定義 連通且不含圈的無向圖稱為 樹 ．常用 T表示 . 樹中的邊稱為 樹枝 . 樹中度為 1的頂點(diǎn)稱為 樹葉 .孤立頂點(diǎn)稱為 平凡樹 .平凡樹定理 2 設(shè) G是具有 n個頂點(diǎn)的圖，則下述命題等價：1) G是樹（ G無圈且連通）；2) G無圈，且有 n1條邊；3) G連通，且有 n1條邊；4) G無圈，但添加任一條新邊恰好產(chǎn)生一個圈 。具有單向歐拉回路的圖稱為 歐拉圖 。若 有兩個奇度頂點(diǎn) ,則它們是每條 歐拉通路的端點(diǎn) .推論 無向圖 G為歐拉圖 (具有歐拉回路 )當(dāng)且僅當(dāng)G是連通的 ,且 G中無奇度頂點(diǎn) .有向圖的 Euler圖給定 G是一個無孤立結(jié)點(diǎn)的有向圖，若存在一條 單向通路 (回路 )，經(jīng)過圖中每邊一次且僅僅一次，則稱此單向通路 (回路 )為該圖的一條 單向歐拉通路 (回路 )。圖論在建模中的應(yīng)用下回停 1. 圖論的基本概念2. 最短路問題及算法 圖論模型基礎(chǔ)知識3. 最小生成樹問題及算法 4. 哈密爾頓圖5. 歐拉圖1) 圖的概念2) 賦權(quán)圖與子圖3) 圖的矩陣表示4) 圖的頂點(diǎn)度5) 路和連通1) 圖的概念 定義 一個 圖 G是指一個二元組 (V(G),E(G))，其中 : 其中元素稱為圖 G的 頂點(diǎn) .組成的集合，即稱為 邊集 ,其中元素稱為 邊 . 定義 圖 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ù) 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)出的子圖 ，記為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1