【正文】 5) G連通，且刪去一條邊就不連通了（即 G為 最最小連通圖 ）；6) G中任意兩頂點間有唯一一條路 .2）圖的生成樹定義 若 T是包含圖 G的全部頂點的子圖 ,它又是樹 ,則稱 T是 G的 生成樹 . 圖 G中不在生成樹的邊叫做 弦 .定理 3 圖 G=(V,E)有生成樹的充要條件是圖 G是連 通的 .（ II）找圖中生成樹的方法可分為兩種：避圈法和破圈法 A 避圈法 : 深探法和廣探法 B 破圈法 A 避圈法 定理 3提供了一種構(gòu)造圖的生成樹的方法 . 這種方法就是在已給的圖 G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠 n1條邊為止 . 這種方法可稱為 “避圈法 ”或 “加邊法 ” 在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種： 深探法 和 廣探法 .B 破圈法 相對于避圈法，還有一種求生成樹的方法叫做 “破圈法 ”. 這種方法就是在圖 G中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復(fù)這個步驟直到圖 G中沒有圈為止 .例 用破圈法求出下圖的一棵生成樹 .B 破圈法例 用破圈法求出下圖的另一棵生成樹 .不難發(fā)現(xiàn)，圖的生成樹不是唯一的 .3) 最小生成樹與算法 介紹最小樹的兩種算法：Kruskal(克魯斯卡） 算法 （或 避圈法 ）和 破圈法 . A Kruskal算法（或避圈法）步驟如下： 1) 選擇邊 e1，使得 w(e1)盡可能??；2) 若已選定邊 ，則從中選取 ，使得 :i) 為無圈圖， ii) 是滿足 i)的盡可能小的權(quán)， 3) 當(dāng)?shù)?2)步不能繼續(xù)執(zhí)行時，則停止 .定理 4 由 Kruskal算法構(gòu)作的任何生成樹都是最小樹 .例 10用 Kruskal算法求下圖的最小樹 .在左圖中 權(quán)值最小的邊有 任取一條 在 中選取權(quán)值最小的邊 中權(quán)值最小邊有 , 從中選任取一條邊會與已選邊構(gòu)成圈 ,故停止 ,得中選取在中選取 中選取 . 但 與 都B破圈法算法 2 步驟如下： 1) 從圖 G中任選一棵樹 T1.2) 加上一條弦 e1， T1+e1中 立即生成一個圈 . 去掉此 圈中最大權(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)是連通無向圖，包含圖 G的每個頂點的路稱為 G的 哈密爾頓路 (Hamilton路 或 H路). 包含圖 G的每個頂點的圈，稱為 G的 哈密爾頓圈(或 Hamilton圈 或 H圈 ). 含 Hamilton圈的圖稱為 哈密爾頓圖 (或 Hamilton圖 或 H圖 ). 4 哈密爾頓圖著名的問題：旅行商問題5 Euler（歐拉）圖哥尼斯堡七橋問題：無向圖的歐拉通路、歐拉圖（即一筆畫問題）經(jīng)過圖中每條邊一次且僅一次并且行遍圖中每個頂點的通路 (回路),稱為 歐拉通路 或歐拉跡 (歐拉回路或歐拉閉跡 ).存在歐拉回路的圖 ,稱為 歐拉圖 .定理 無向圖 G具有 歐拉通路 ,當(dāng)且僅當(dāng) G是連通圖且 有零個或兩個奇度頂點 .若 無奇度頂點 ,則通路 為回路 。若 有兩個奇度頂點 ,則它們是每條 歐拉通路的端點 .推論 無向圖 G為歐拉圖 (具有歐拉回路 )當(dāng)且僅當(dāng)G是連通的 ,且 G中無奇度頂點 .有向圖的 Euler圖給定 G是一個無孤立結(jié)點的有向圖，若存在一條 單向通路 (回路 )，經(jīng)過圖中每邊一次且僅僅一次，則稱此單向通路 (回路 )為該圖的一條 單向歐拉通路 (回路 )。 選址問題 重心問題3．最小生成樹及算法1) 樹的定義與樹的特征定義 連通且不含圈的無向圖稱為 樹 ．常用 T表示 . 樹中的邊稱為 樹枝 . 樹中度為 1的頂點稱為 樹葉 .孤立頂點稱為 平凡樹 .