【正文】 其要點(diǎn)如下 : (1) 把 V分成兩個(gè)子集 S和 T?？梢娨陨蠑嘌猿闪?。 置 S為 S∪ {x}={a,v1},置 T為 T{x}={v2,v3,v4}。 穿程于圖 G的每條邊一次且僅一次的路徑 ,稱為歐拉路徑。如果歐拉路徑的兩端點(diǎn)不同 ,那么它們就是僅有的兩個(gè)奇數(shù)頂點(diǎn) ,如果它們是重合的 ,那么所有頂點(diǎn)都有偶數(shù)次數(shù) ,并且這條歐拉路徑成為一條歐拉回路。如果圖中不是所有邊被畫過 ,我們?nèi)サ粢旬嬤^ 的邊 ,得到由剩下邊組成的一個(gè)子圖 ,這個(gè)子圖的頂點(diǎn)次數(shù)全是偶數(shù)。例如 ,圖 ―9( a)和 (b)均可一筆畫成 ,因?yàn)榉洗嬖跉W拉路徑和歐拉回路條件。 旋轉(zhuǎn)鼓的表面分成 8塊扇形 ,如圖 ―10 所示。它的問題如下 : 如何沿 12面體的棱線 ,通過每個(gè)角一次且僅一次 ?(稱為環(huán)游全世界游戲 。 第 8章 圖論 圖 ―13 第 8章 圖論 定理 ―6 中的條件不是充分的 ,圖 ―5 中給出的彼得森圖 ,它對任意 SV都滿足 ω(GS)≤|S|,但不是哈密爾頓圖。證畢。 第 8章 圖論 至今未找出有效的方法 ,但已找到了若干近似算法 ,現(xiàn)介紹其一 ——最鄰近算法 ,它為巡回售貨員問題得出一個(gè)近似解。 二部圖可記為 G=〈 X,E,Y〉 ,X和 Y稱為互補(bǔ)結(jié)點(diǎn)子集 。 求最大匹配要應(yīng)用交替鏈概念 ,其定義如下 。 第 8章 圖論 例如 ,在下圖中 ,可用如下標(biāo)記過程 : (1) 把 x’2標(biāo)記 (*)。但 M′比 M多一條邊。所以M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}就是所求的最大匹配。這是因?yàn)樘砣氲倪呑陨聿幌嘟?,又不與 M中不屬于 γ的邊相交。 Ⅱ .選一個(gè) Y的新標(biāo)記過的結(jié)點(diǎn) ,比如說 yi,用 (yi)標(biāo)記通過 M的邊與 yi鄰接且未標(biāo)記過的 X的所有結(jié)點(diǎn)。含有最多邊數(shù)的匹配稱為 G的最大匹配。 例如 ,對于圖 ―15( a)所示的圖 ,如果我們從 a點(diǎn)開始 ,根據(jù)最鄰近算法構(gòu)造一個(gè)哈密爾頓回路 ,過程如圖 (b)到 (e)所示 ,所得回路的總距離是 44, 其實(shí)圖 ―15( a)的最小哈密爾頓回路應(yīng)如 (f)所示 ,總距離是 43。每兩城市間都有一條直接通路 ,我們記 vi城市到 vj城市的距離為 W(i,j),問題是去設(shè)計(jì)一個(gè)算法 ,它將找出售貨員能采取的最短路徑。 若不然 ,設(shè)在 G′中 v1與 相鄰 ,而 vn與 都不相鄰 ,則 deg(vn)≤nk1,這樣 deg(v1)+deg(vn)≤n1＜ n,與題設(shè)不符。 證用 A標(biāo)記頂點(diǎn) a,所有與 A鄰接的頂點(diǎn)標(biāo)記為 B。具有哈密爾頓回路的圖稱為哈密爾頓圖。 第 8章 圖論 例 3布魯英 (DeBruijn)序列。 第 8章 圖論 例 2 (a)一筆畫問題。因此 ,這樣的構(gòu)造過程一定以到達(dá)另一個(gè)奇數(shù)次數(shù)頂點(diǎn)而告終 (若無奇數(shù)次數(shù)的頂點(diǎn) ,則以回到原出發(fā)點(diǎn)而告終 )。如果圖具有歐拉路徑 ,那么順著這條路徑畫出的時(shí)候 ,每次碰到一個(gè)頂點(diǎn) ,都需通過關(guān)聯(lián)于這個(gè)頂點(diǎn)的兩條邊 ,并且這兩條邊在以前未畫過。 1736年歐拉用圖論方法解決了此問題 ,寫了第一篇圖論的論文 ,從而成為圖論的創(chuàng)始人。 第 8章 圖論 例 1 考慮圖 ―7 中的圖 ,起初 S={a},T={v1,v2,v3,v4},D(a)=0,D(v1)=2,D(v2)=+∞,D(v3)=+∞,D(v4)=10。 首先我們證明 “ 若 x是 T中具有最小 D值的結(jié)點(diǎn) ,則D(x)是從 a到 x的距離 ” ,用反證法。路徑 P的長度定義為路徑中邊的長度之和 ,記為 W(P)。 第 8章 圖論 定理 ―3 設(shè) G是任一 (n,m)無向簡單圖 ,ω是 其分圖個(gè)數(shù) ,則 1 ( )( 1 )2n m n n? ? ?? ? ? ? ? ? 定義 ―6 在有向圖中 ,如果在任兩結(jié)點(diǎn)偶對中 ,至少從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的 ,則稱圖 G是單向連通的 。 (2) d(vi,vi)=0。 ) 定理 ―1 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的簡單圖 G=〈 V,E〉中 ,如果從 v1到 v2有一條路徑 ,則從 v1到 v2有一條長度不大于 n1的基本路徑。 第 8章 圖論 如果路徑的始點(diǎn) v0和終點(diǎn) vn相重合 ,即 v0=vn,則此路徑稱為 回路 ,沒有相同邊的回路稱為簡單回路 ,通過各頂點(diǎn)不超過一次的回路稱為基本回路。 ? ?? ? ?? (4)若在子圖 G′中 ,對 V′中的任意二結(jié)點(diǎn) u、 v,當(dāng) ［ u,v］ ∈ E時(shí)有［ u,v］ ∈ E′,則 G′由 V′唯一確定 , 此時(shí)稱 G′為由結(jié)點(diǎn)集 V′導(dǎo)出的子圖。 (2)刪去圖 G的一個(gè)結(jié)點(diǎn) v。 (a)中的 x應(yīng)與 (b)中的 y對應(yīng) ,因?yàn)榇螖?shù)都是 3。 第 8章 圖論 例 2 (a)、 (b)兩圖是同構(gòu)的。所以 前一項(xiàng)次數(shù)為偶數(shù) 。結(jié)點(diǎn) v的引出次數(shù)和引入次數(shù)之和稱為結(jié)點(diǎn)v的 次數(shù) (或度數(shù) ),記作 deg(v)。 定義 ―2 含有平行邊的圖稱為 多重圖 。這個(gè)無向圖習(xí)慣上叫做該 有向圖的底圖 。無向邊簡稱棱 ,除無始點(diǎn)和終點(diǎn)的術(shù)語外 ,其它術(shù)語與有向邊相同。若沒有一個(gè)地 方通奇數(shù)座橋，則從任何一地出發(fā)，所求的路線都能實(shí)現(xiàn) 第 8章 圖論 定義 ―1 一個(gè) 圖 G是一個(gè)三重組 〈 V(G),E(G),ΦG〉 ,其中V(G)是一個(gè)非空的 結(jié)點(diǎn) (或叫頂點(diǎn) )集合 ,E(G)是 邊 的集合 ,ΦG是從邊集 E到結(jié)點(diǎn)偶對集合上的函數(shù)。如果只有兩個(gè)地方通奇數(shù)座橋，則可從其中任何一地出發(fā)找到所要求的路線。若邊 e所對應(yīng)的偶對 (a,b)是無序的 ,則稱 e是 無向邊 。又如 ,把有向圖中每條有向邊都看作無向邊 ,就得到無向圖。僅有一條時(shí)重?cái)?shù)為 1,無邊時(shí)重?cái)?shù)為 0。以 v為終點(diǎn)的邊的條數(shù)稱為結(jié)點(diǎn) v的 引入次數(shù) (或入度 ),記為 deg(v)。 由上一定理得 iE?iO?121 1 12 d eg ( ) d eg ( ) d eg ( )iinnni E Oi i im ? ? ?? ? ?? ? ?? ? ? 因?yàn)榇螖?shù)為偶數(shù)的各結(jié)點(diǎn)次數(shù)之和為偶數(shù)。 上述定義說明 ,兩個(gè)圖的各結(jié)點(diǎn)之間 ,如果存在一一對應(yīng)關(guān)系 ,而且這種對應(yīng)關(guān)系保持了結(jié)點(diǎn)間的鄰接關(guān)系(在有向圖時(shí)還保持邊的方向 )和邊的重?cái)?shù) ,則這兩個(gè)圖是同構(gòu)的 ,兩個(gè)同構(gòu)的圖除了頂點(diǎn)和邊的名稱不同外實(shí)際上代表同樣的 組合結(jié)構(gòu)。例如下圖中 (a)、 (b)兩圖雖然滿足以上3條件 ,但不同構(gòu)。 ?第 8章 圖論 除以上 4種運(yùn)算外 ,還有以下兩種操作 :