圖論講稿-資料下載頁(yè)
2025-01-20 12:54本頁(yè)面
【正文】 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,得到一棵新樹仍是原來(lái)的樹； 再加上弦 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) ,則通路 為回路 。若 有兩個(gè)奇度頂點(diǎn) ,則它們是每條 歐拉通路的端點(diǎn) .推論 無(wú)向圖 G為歐拉圖 (具有歐拉回路 )當(dāng)且僅當(dāng)G是連通的 ,且 G中無(wú)奇度頂點(diǎn) .有向圖的 Euler圖給定 G是一個(gè)無(wú)孤立結(jié)點(diǎn)的有向圖，若存在一條 單向通路 (回路 )，經(jīng)過圖中每邊一次且僅僅一次，則稱此單向通路 (回路 )為該圖的一條 單向歐拉通路 (回路 )。具有單向歐拉回路的圖稱為 歐拉圖 。定理 一個(gè)有向圖 D具有歐拉通路 ,當(dāng)且僅當(dāng) D是連通 的 ,且除了兩個(gè)頂點(diǎn)外 ,其余頂點(diǎn)的 入度均等于出度 .這兩個(gè)特殊的頂點(diǎn)中 ,一個(gè)頂點(diǎn)的 入度比出度大 ⒈ 另一個(gè)頂點(diǎn)的 入度比出度小 1.有向圖的 Euler圖 推論 一個(gè)有向圖 D是 歐拉圖 (具有歐拉回路 ),當(dāng)且僅當(dāng) D是 連通 的 ,且所有頂點(diǎn)的 入度等于出度 . 只具歐拉通路 ,無(wú)歐拉回路的圖不是歐拉圖 .謝謝！演講完畢，謝謝觀看！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1