【正文】 5) G連通，且刪去一條邊就不連通了（即 G為 最最小連通圖 ）；6) G中任意兩頂點(diǎn)間有唯一一條路 .2）圖的生成樹(shù)定義 若 T是包含圖 G的全部頂點(diǎn)的子圖 ,它又是樹(shù) ,則稱 T是 G的 生成樹(shù) . 圖 G中不在生成樹(shù)的邊叫做 弦 .定理 3 圖 G=(V,E)有生成樹(shù)的充要條件是圖 G是連 通的 .（ II）找圖中生成樹(shù)的方法可分為兩種：避圈法和破圈法 A 避圈法 : 深探法和廣探法 B 破圈法 A 避圈法 定理 3提供了一種構(gòu)造圖的生成樹(shù)的方法 . 這種方法就是在已給的圖 G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠 n1條邊為止 . 這種方法可稱為 “避圈法 ”或 “加邊法 ” 在避圈法中，按照邊的選法不同，找圖中生成樹(shù)的方法可分為兩種： 深探法 和 廣探法 .B 破圈法 相對(duì)于避圈法，還有一種求生成樹(shù)的方法叫做 “破圈法 ”. 這種方法就是在圖 G中任取一個(gè)圈，任意舍棄一條邊，將這個(gè)圈破掉，重復(fù)這個(gè)步驟直到圖 G中沒(méi)有圈為止 .例 用破圈法求出下圖的一棵生成樹(shù) .B 破圈法例 用破圈法求出下圖的另一棵生成樹(shù) .不難發(fā)現(xiàn)，圖的生成樹(shù)不是唯一的 .3) 最小生成樹(shù)與算法 介紹最小樹(shù)的兩種算法：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)作的任何生成樹(shù)都是最小樹(shù) .例 10用 Kruskal算法求下圖的最小樹(shù) .在左圖中 權(quán)值最小的邊有 任取一條 在 中選取權(quán)值最小的邊 中權(quán)值最小邊有 , 從中選任取一條邊會(huì)與已選邊構(gòu)成圈 ,故停止 ,得中選取在中選取 中選取 . 但 與 都B破圈法算法 2 步驟如下： 1) 從圖 G中任選一棵樹(shù) T1.2) 加上一條弦 e1， T1+e1中 立即生成一個(gè)圈 . 去掉此 圈中最大權(quán)邊，得到新樹(shù) T2,以 T2代 T1,重復(fù) 2)再檢查剩余的弦，直到全部弦檢查完畢為止 .例 11用破圈法求下圖的最小樹(shù) .先求出上圖的一棵生成樹(shù) . 加以弦 e2,得到的圈 v1v3v2v1,去掉最大的權(quán)邊 e2,得到一棵新樹(shù)仍是原來(lái)的樹(shù)； 再加上弦 e7，得到圈 v4v5v2v4,去掉最大的權(quán)邊 e6，得到一棵新樹(shù)；如此重復(fù)進(jìn)行，直到全全部的弦均已試過(guò) ,得 最小樹(shù) . 定義 設(shè) G=(V,E)是連通無(wú)向圖，包含圖 G的每個(gè)頂點(diǎn)的路稱為 G的 哈密爾頓路 (Hamilton路 或 H路). 包含圖 G的每個(gè)頂點(diǎn)的圈，稱為 G的 哈密爾頓圈(或 Hamilton圈 或 H圈 ). 含 Hamilton圈的圖稱為 哈密爾頓圖 (或 Hamilton圖 或 H圖 ). 4 哈密爾頓圖著名的問(wèn)題：旅行商問(wèn)題5 Euler（歐拉）圖哥尼斯堡七橋問(wèn)題：無(wú)向圖的歐拉通路、歐拉圖（即一筆畫(huà)問(wèn)題）經(jīng)過(guò)圖中每條邊一次且僅一次并且行遍圖中每個(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)過(guò)圖中每邊一次且僅僅一次，則稱此單向通路 (回路 )為該圖的一條 單向歐拉通路 (回路 )。 選址問(wèn)題 重心問(wèn)題3．最小生成樹(shù)及算法1) 樹(shù)的定義與樹(shù)的特征定義 連通且不含圈的無(wú)向圖稱為 樹(shù) ．常用 T表示 . 樹(shù)中的邊稱為 樹(shù)枝 . 樹(shù)中度為 1的頂點(diǎn)稱為 樹(shù)葉 .孤立頂點(diǎn)稱為 平凡樹(shù) .