圖論講稿(參考版)
2025-01-22 12:54本頁(yè)面
【正文】 具有單向歐拉回路的圖稱為 歐拉圖 。 5) G連通，且刪去一條邊就不連通了（即 G為 最最小連通圖 ）；6) G中任意兩頂點(diǎn)間有唯一一條路 .2）圖的生成樹定義 若 T是包含圖 G的全部頂點(diǎn)的子圖 ,它又是樹 ,則稱 T是 G的 生成樹 . 圖 G中不在生成樹的邊叫做 弦 .定理 3 圖 G=(V,E)有生成樹的充要條件是圖 G是連 通的 .（ II）找圖中生成樹的方法可分為兩種：避圈法和破圈法 A 避圈法 : 深探法和廣探法 B 破圈法 A 避圈法 定理 3提供了一種構(gòu)造圖的生成樹的方法 . 這種方法就是在已給的圖 G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠 n1條邊為止 . 這種方法可稱為 “避圈法 ”或 “加邊法 ” 在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種： 深探法 和 廣探法 .B 破圈法 相對(duì)于避圈法，還有一種求生成樹的方法叫做 “破圈法 ”. 這種方法就是在圖 G中任取一個(gè)圈，任意舍棄一條邊，將這個(gè)圈破掉，重復(fù)這個(gè)步驟直到圖 G中沒有圈為止 .例 用破圈法求出下圖的一棵生成樹 .B 破圈法例 用破圈法求出下圖的另一棵生成樹 .不難發(fā)現(xiàn)，圖的生成樹不是唯一的 .3) 最小生成樹與算法 介紹最小樹的兩種算法：Kruskal(克魯斯卡） 算法 （或 避圈法 ）和 破圈法 . A Kruskal算法（或避圈法）步驟如下： 1) 選擇邊 e1，使得 w(e1)盡可能小；2) 若已選定邊 ，則從中選取 ，使得 :i) 為無(wú)圈圖， ii) 是滿足 i)的盡可能小的權(quán)， 3) 當(dāng)?shù)?2)步不能繼續(xù)執(zhí)行時(shí)，則停止 .定理 4 由 Kruskal算法構(gòu)作的任何生成樹都是最小樹 .例 10用 Kruskal算法求下圖的最小樹 .在左圖中 權(quán)值最小的邊有 任取一條 在 中選取權(quán)值最小的邊 中權(quán)值最小邊有 , 從中選任取一條邊會(huì)與已選邊構(gòu)成圈 ,故停止 ,得中選取在中選取 中選取 . 但 與 都B破圈法算法 2 步驟如下： 1) 從圖 G中任選一棵樹 T1.2) 加上一條弦 e1， T1+e1中 立即生成一個(gè)圈 . 去掉此 圈中最大權(quán)邊，得到新樹 T2,以 T2代 T1,重復(fù) 2)再檢查剩余的弦，直到全部弦檢查完畢為止 .例 11用破圈法求下圖的最小樹 .先求出上圖的一棵生成樹 . 加以弦 e2,得到的圈 v1v3v2v1,去掉最大的權(quán)邊 e2,得到一棵新樹仍是原來的樹； 再加上弦 e7，得到圈 v4v5v2v4,去掉最大的權(quán)邊 e6，得到一棵新樹；如此重復(fù)進(jìn)行，直到全全部的弦均已試過 ,得 最小樹 . 定義 設(shè) G=(V,E)是連通無(wú)向圖，包含圖 G的每個(gè)頂點(diǎn)的路稱為 G的 哈密爾頓路 (Hamilton路 或 H路). 包含圖 G的每個(gè)頂點(diǎn)的圈，稱為 G的 哈密爾頓圈(或 Hamilton圈 或 H圈 ). 含 Hamilton圈的圖稱為 哈密爾頓圖 (或 Hamilton圖 或 H圖 ). 4 哈密爾頓圖著名的問題：旅行商問題5 Euler（歐拉）圖哥尼斯堡七橋問題：無(wú)向圖的歐拉通路、歐拉圖（即一筆畫問題）經(jīng)過圖中每條邊一次且僅一次并且行遍圖中每個(gè)頂點(diǎn)的通路 (回路),稱為 歐拉通路 或歐拉跡 (歐拉回路或歐拉閉跡 ).存在歐拉回路的圖 ,稱為 歐拉圖 .定理 無(wú)向圖 G具有 歐拉通路 ,當(dāng)且僅當(dāng) G是連通圖且 有零個(gè)或兩個(gè)奇度頂點(diǎn) .若 無(wú)奇度頂點(diǎn) ,則通路 為回路 。圖論在建模中的應(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) .組成的集合，即稱為 邊集 ,其中元素稱為 邊 .
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1