離散數(shù)學(xué)E圖和H.ppt

2020 2 5 離散數(shù)學(xué) 1 第八章E圖和H圖 2020 2 5 離散數(shù)學(xué) 2 8 1七橋問(wèn)題與E圖 七橋問(wèn)題 有四塊陸地與連結(jié)它們的七座橋 問(wèn)能否從這四塊陸地中的任意一塊出發(fā) 經(jīng)過(guò)每一座橋恰好一次 最后回到原地 2020 2 5 離散數(shù)學(xué) 3 一筆畫(huà) 該問(wèn)題等價(jià)于 能否一筆畫(huà)出下圖 Euler證明了 七橋問(wèn)題是無(wú)解的 圖中 頂點(diǎn)表示陸地 邊表示陸地之間的橋 2020 2 5 離散數(shù)學(xué) 4 E圖 定義8 1 1 設(shè)G是一個(gè)圖 經(jīng)過(guò)G的每一條邊的鏈稱(chēng)為E鏈 閉的E鏈稱(chēng)為E閉鏈 如果G中存在E鏈 稱(chēng)G為半E圖 如果G中存在E閉鏈 稱(chēng)G為E圖 下面的討論中設(shè)G是非平凡的連通圖 2020 2 5 離散數(shù)學(xué) 5 無(wú)奇點(diǎn)的連通圖是E圖 引理8 1 1 連通圖G中無(wú)奇點(diǎn) 則G是E圖 證明 設(shè)G是無(wú)奇點(diǎn)的連通圖且G不是E圖 在所有連通無(wú)奇點(diǎn)的非E圖中 選一個(gè)邊最少的圖G 因G的每個(gè)頂點(diǎn)的度至少是2 從而G必含閉鏈 為什么 若G不含回路 則G是樹(shù) 我們知道樹(shù)中至少有兩個(gè)懸掛點(diǎn) 奇點(diǎn) 矛盾 所以G中一定含有回路 而回路就是閉鏈 如果回路之間有重復(fù)出現(xiàn)的邊 我們可以去掉重復(fù)者 使每條邊僅出現(xiàn)一次 這樣就得到了一條閉鏈 所以G中必含閉鏈 設(shè)C是G中最長(zhǎng)的閉鏈 由假設(shè)C不是E閉鏈 于是G E C 中必含非平凡連通分支G 且G 中無(wú)奇點(diǎn) 顯然q G q G 為什么 故G 必是E圖 由G和C的選法 于是G 有一條E閉鏈C 因G連通 C 和C必有公共點(diǎn)v 以v作為C C的起 終點(diǎn) 于是C C是G的一條閉鏈且長(zhǎng)度大于C的長(zhǎng)度 這與C的假設(shè)矛盾 故G是E圖 因G不是E圖 G無(wú)奇點(diǎn)且C無(wú)奇點(diǎn) 2020 2 5 離散數(shù)學(xué) 6 C C G v G G中含閉鏈圖示 C C 是一條閉鏈圖示 2020 2 5 離散數(shù)學(xué) 7 E圖是無(wú)奇點(diǎn)的連通圖 引理8 1 1 E圖是無(wú)奇點(diǎn)的連通圖 證明 設(shè)G是E圖 C是G的一條E閉鏈 由于G連通且C是含G的每邊恰一次的閉鏈 因此 C中的每個(gè)點(diǎn)都既是起點(diǎn)也是終點(diǎn) 于是 從C上的任一點(diǎn)u出發(fā) 每經(jīng)過(guò)一個(gè)頂點(diǎn)v 就有兩條與v關(guān)聯(lián)的邊出現(xiàn) 一進(jìn)一出 這樣 C上的每個(gè)頂點(diǎn) 也即G的每個(gè)頂點(diǎn)的度均為偶數(shù) 故G中無(wú)奇點(diǎn) 由引理8 1 1和8 1 1 我們有 定理8 1 1 連通圖G是E圖當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn) 2020 2 5 離散數(shù)學(xué) 8 半E圖中最多有兩個(gè)奇點(diǎn) 推論8 1 1 G是半E圖當(dāng)且僅當(dāng)G中最多有兩個(gè)奇點(diǎn) 證明 必要性 設(shè)G是半E圖 C是G的一條E鏈 除起點(diǎn)與終點(diǎn)外 C中每個(gè)頂點(diǎn)的度均為偶數(shù) 又因G連通 故G最多有兩個(gè)奇點(diǎn) 充分性 設(shè)G最多只有兩個(gè)奇點(diǎn) 若G無(wú)奇點(diǎn) 則由定理8 1 1知 G為E圖 亦為半E圖 若G有兩個(gè)奇點(diǎn) 設(shè)為u和v 則在G中加入e uv的邊 使G中無(wú)奇點(diǎn) 由定理8 1 1知 G e為E圖 即G e含E閉鏈C 于是C e構(gòu)成G的一條E鏈 所以G是半E圖 2020 2 5 離散數(shù)學(xué) 9 哥尼斯城堡橋不是E圖 半E圖 2020 2 5 離散數(shù)學(xué) 10 8 2周游世界問(wèn)題與H圖 周游世界問(wèn)題 用一個(gè)正十二面體的二十個(gè)頂點(diǎn)來(lái)代表二十個(gè)城市 要求從其中任一頂點(diǎn)出發(fā) 沿著這個(gè)正十二面體的棱走遍這二十個(gè)頂點(diǎn) 且每個(gè)城市只經(jīng)過(guò)一次 最后回到起點(diǎn) 該問(wèn)題等價(jià)于 能否從下圖找一條含所有頂點(diǎn)的回路 2020 2 5 離散數(shù)學(xué) 11 H圖 定義8 2 1 設(shè)G是一個(gè)圖 含G的每個(gè)頂點(diǎn)的通路稱(chēng)為H通路 起點(diǎn)與終點(diǎn)重合的H通路稱(chēng)為H回路 如果G中存在H回路 稱(chēng)G為H圖 若G中存在H通路 稱(chēng)G為半H圖 說(shuō)明 H圖必是半H圖 反之不然 2020 2 5 離散數(shù)學(xué) 12 Herschel圖 該圖是半H圖 因?yàn)樗且粋€(gè)具有奇數(shù)個(gè)頂點(diǎn)的二分圖 所以不可能有H回路 因?yàn)槎謭D中的回路一定是偶數(shù)條邊 定理5 5 2 2020 2 5 離散數(shù)學(xué) 13 H圖的一個(gè)必要條件 定理8 2 1如果G是一個(gè)H圖 則對(duì)V G 的任何非空真子集S 均成立 G S S 8 1 證明 設(shè)C是G的H回路 G的所有頂點(diǎn)都在C上 則顯然有 C S S 成立 其中 S V G 由于C S是G S的生成子圖 C S的連通分支數(shù)不比G S的少 因此 G S C S S 故 8 1 式成立 2020 2 5 離散數(shù)學(xué) 14 G H圖 C H回路 定理8 2 1證明圖示 2020 2 5 離散數(shù)學(xué) 15 一個(gè)非H圖的判定 取S為紅色點(diǎn)集 S 5 G S 6 S 根據(jù)定理8 2 1 此圖不是H圖 2020 2 5 離散數(shù)學(xué) 16 注意 這只是必要條件 注意定理8 2 1只是判斷H圖的必要條件 有的圖雖然滿足條件 卻不是H圖 如右邊的Peterson圖不是H圖 可是它卻滿足定理8 2 1的條件 Peterson圖 Peterson圖是半H圖而不是H圖 2020 2 5 離散數(shù)學(xué) 17 H圖的一個(gè)充分條件 定理8 2 2 設(shè)G是p 3 階簡(jiǎn)單圖 如果G中任何兩個(gè)不鄰接的頂點(diǎn)u和v均滿足 d u d v p 8 2 則G是H圖 證明 若滿足 8 2 的簡(jiǎn)單圖不是H圖 令G p q 是其中邊數(shù)最多的一個(gè)圖 顯然 G Kp 因?yàn)镵p一定是H圖 設(shè)u v是G中不鄰接的兩個(gè)頂點(diǎn) 由G的假設(shè)可知 G uv是H圖 且其中的H回路必含uv 于是 G中存在從u到v的H通路P v1v2 vp 其中u v1 v vp 2020 2 5 離散數(shù)學(xué) 18 H圖的一個(gè)充分條件 證明 H通路P v1v2 vp 其中u v1 v vp 令S vi v1vi E G T vi vi 1vp E G S是鄰接u的點(diǎn)的集合 T是位于鄰接v的頂點(diǎn)的后面的頂點(diǎn)的集合 由G是簡(jiǎn)單圖知 S d u T d v 又由v1與vp不鄰接有S v2 vp 1 以及T v3 vp 從而S T v2 v3 vp S T p 2020 2 5 離散數(shù)學(xué) 19 H圖的一個(gè)充分條件 證明 S T p 而S T 若不然 設(shè)vi S T 則存在v1v2 vi 1vpvp 1 viv1將是G的H回路 此與G不是H圖的假設(shè)相矛盾 u v1 v2 vi 1 vi vi 1 vp 1 vp v G uv中的H回路 G中的H回路 2020 2 5 離散數(shù)學(xué) 20 H圖的一個(gè)充分條件 定理8 2 2 設(shè)G是p 3 階簡(jiǎn)單圖 如果G中任何兩個(gè)不鄰接的頂點(diǎn)u和v均滿足 d u d v p 8 2 則G是H圖 證明 S d u T d v S T p S T 于是 p d v1 d vp S T S T p 此為矛盾 故結(jié)論成立 2020 2 5 離散數(shù)學(xué) 21 定理8 2 2的條件不是必要的 例如下圖是H圖但任意兩頂點(diǎn)度之和為4 而P 5 2020 2 5 離散數(shù)學(xué) 22 H圖的又一個(gè)充分條件 推論8 2 1設(shè)G是p 3 階簡(jiǎn)單圖 如果 G P 2 則G是H圖 證明 任取u v V G 由題設(shè)均有d u d v p 2 p 2 p因此 由定理8 2 2知 G是H圖 2020 2 5 離散數(shù)學(xué) 23 圖的閉包 定義8 2 2 設(shè)A是p階圖 對(duì)A中滿足 d u d v p 8 3 的頂點(diǎn)u v 若uv E A 則將邊uv加入到A中 得到A uv 如此反復(fù)加邊 直到所有滿足 8 3 的點(diǎn)都鄰接 最后所得的圖稱(chēng)為A的閉包 記為 由于一個(gè)圖的閉包是唯一的 所以求閉包時(shí)加邊的順序可以任意 2020 2 5 離散數(shù)學(xué) 24 求一個(gè)圖的閉包 例 求右圖的閉包 v1 v2 v3 v4 v5 v6 d v1 d v4 6 連接v1和v4 d v3 d v5 6 連接v3和v5 d v3 d v6 6 連接v3和v6 d v4 d v6 6 連接v4和v6 d v4 d v2 6 連接v4和v2 d v5 d v2 6 連接v5和v2 d v6 d v2 6 連接v6和v2 存在A 的情形 A Kp A中無(wú)滿足條件的邊可加 如圖G G 2020 2 5 離散數(shù)學(xué) 25 H圖的充要條件 引理8 2 1設(shè)G是p階簡(jiǎn)單圖 u與v是G中兩個(gè)不鄰接的頂點(diǎn)且滿足 d u d v p于是 G是H圖當(dāng)且僅當(dāng)G uv是H圖 證明 設(shè)G是H圖 則G uv顯然也是H圖 反之 假設(shè)G uv是H圖 如果其中一條H回路不含uv 則G必是H圖 如果G uv中所有H回路均含邊uv 設(shè)其中有一條回路為C v1v2v3v4 vpv1 其中v1 u v2 v 2020 2 5 離散數(shù)學(xué) 26 H圖的充要條件 證明 C v1v2 vpv1 其中v1 u v2 v 記 d u dG uv u dG u 1 d v dG uv v dG v 1 則有d u d v dG u dG v 2 p 2 8 4 假設(shè)在頂點(diǎn)v3 v4 vp 1中有r個(gè)頂點(diǎn) vi1 vi2 vir與u鄰接 則dG uv u r 2 u與v2 vp鄰接 于是 頂點(diǎn)v必與r個(gè)頂點(diǎn)vi1 1 vi2 1 vir 1 8 5 中的某個(gè)頂點(diǎn)vij 1鄰接 若p 4 且在G中u v分別只與vp和v3鄰接 則dG u dG v 2 p 與條件矛盾 故要么u與 v3 vp 1 中的r個(gè)頂點(diǎn)鄰接 要么v與 v4 vp 中的r個(gè)頂點(diǎn)鄰接 且r p 2 2 dG u r 1 dG v r 1 dG u dG v 2r 2 p 故r p 2 2 2020 2 5 離散數(shù)學(xué) 27 H圖的充要條件 證明 頂點(diǎn)v必與 8 5 中某頂點(diǎn)vij 1相鄰接 如果v不與 8 5 中的任何頂點(diǎn)鄰接 則有dG uv v p 1 r p 1 dG uv u 2 因此 dG uv v dG uv u p 1 此與 8 4 矛盾 因此 C v1vijvij 1 v3v2vij 1 vpv1就是G的一條H回路 C 恰不包含邊uv 即G為H圖 v2 v vp v1 vij 1 vij 1 vij v1 u G uv的H回路 G的H回路 P 1是G的最大度 2020 2 5 離散數(shù)學(xué) 28 A是H圖當(dāng)且僅當(dāng) 是H圖 定理8 2 3 p階簡(jiǎn)單圖A是H圖當(dāng)且僅當(dāng) 是H圖 證明 設(shè)圖A是H圖 則顯然 也是H圖 反之 設(shè) 是H圖 若A 則A是H圖 若A 則存在ei E A i 1 t t 1 使得A e1 e2 et 設(shè)ei uv 由閉包的定義知 d u d v p 且u與v在A中不鄰接 因?yàn)?是H圖 由引理8 2 1知 et仍是H圖 反復(fù)應(yīng)用該引理 可知A是H圖 2020 2 5 離散數(shù)學(xué) 29 用頂點(diǎn)度序列判斷H圖 定理8 2 4 設(shè)p 3 階簡(jiǎn)單圖G的各頂點(diǎn)度數(shù)序列為d1 d2 dp 于是 若對(duì)任何mm 或者dp m p m 則G是H圖 證明 我們將證明 Kp 從而由定理8 2 3有G是H圖 由推論8 2 1知Kp是H圖 假設(shè) Kp 用d v 記 中v的度數(shù) 設(shè)u和v是 中不鄰接且度數(shù)和為最大的兩個(gè)點(diǎn) 不妨假設(shè)d u d v 由于uv E 因此由閉包的定義有d u d v p 于是d u p 2 取m d u p 2 2020 2 5 離散數(shù)學(xué) 30 用頂點(diǎn)度序列判斷H圖 證明 m d u p 2 設(shè) 為 中不與v鄰接的頂點(diǎn)數(shù) 則d v p 1 即 p 1 d v 而p 1 d u d v 因此 d u m 即 中不與v鄰接的頂點(diǎn)數(shù)至少為m 記為 vi1 vi2 vi m u vi 其中由u的最大性不妨設(shè)d vi1 d vi2 d vi m 由于V G V 因此G中也至少有m個(gè)頂點(diǎn)的度數(shù)不大于m 又因?yàn)镚的度數(shù)序列以遞增順序排列 所以 dm m 2020 2 5 離散數(shù)學(xué) 31 用頂點(diǎn)度序列判斷H圖 證明 dm m 同樣 設(shè)在 中不與u鄰接的頂點(diǎn)數(shù)為 于是 p 1 d u p 1 m 設(shè)這些頂點(diǎn)分別為vj1 vj2 vj v vj 其中由v的假定可設(shè)d vj1 d vj2 d vj d v p m 又m p 2 所以 m m p 0 即d u p m 從而G中共有 p m 1 1 p m個(gè)頂點(diǎn)的度數(shù)均小于p m 即dp m p m 這說(shuō)明存在m p 2使得dm m和dp m p m都成立 此與已知條件矛盾 于是 Kp 定理得證 d v d u p 且d u m 個(gè)頂點(diǎn)加上頂點(diǎn)u 2020 2 5 離散數(shù)學(xué) 32 8 3應(yīng)用 旅行推銷(xiāo)員問(wèn)題 設(shè)有n個(gè)城市C1 Cn 某推銷(xiāo)員從C1出發(fā)推銷(xiāo)產(chǎn)品 每個(gè)城市都要走到一次 最后回到C1 已知每?jī)蓚€(gè)城市之間的距離 問(wèn)怎樣安排行程才能使總路程最短 等價(jià)的圖論語(yǔ)言描述 在賦權(quán)完全圖中求權(quán)最小的H回路 簡(jiǎn)稱(chēng)為最優(yōu)回路 2020 2 5 離散數(shù)學(xué) 33 求最優(yōu)回路 最優(yōu)回路是可解的 最簡(jiǎn)單的方法就是窮舉法 即找出KP的所有H回路 然后從中選出最小者即可 可是對(duì)n 4 個(gè)頂點(diǎn)的完全圖 所有權(quán)可能不等的H回路共有 n 1 種 其時(shí)間復(fù)雜度為O n 所以當(dāng)N較大時(shí) 用窮舉法求解是不可想象的 如何用較快的算法來(lái)求最優(yōu)回路 是人們正在研究且尚未最終解決的問(wèn)題 人們開(kāi)始轉(zhuǎn)而求其次 即尋找一種算法能較快地求出一種較優(yōu)的但不一定是最優(yōu)的解 2020 2 5 離散數(shù)學(xué) 34 逐次改進(jìn)法 逐次改進(jìn)法這是一種近似解法 先找賦權(quán)完全圖G的一條H回路 記為C v1v2 vnv1 如果w vi 1vj 1 w vivj w vi 1vi w vj 1vj 8 6 則用H回路Cij v1v2 vi 1vj 1vj 2 vi 1vivjvj 1 vnv1代替C 反復(fù)應(yīng)用 直到找不出滿足 8 6 式的Cij為止 逐次改進(jìn)法不一定得到最優(yōu)回路 2020 2 5 離散數(shù)學(xué) 35 圖示 逐次改進(jìn)法 任意一條H回路C如圖所示 v1 vj 1 vj 2 vi vi 1 vi 1 vj vj 1 v2 vn 現(xiàn)在找到w vi 1vj 1 w vivj w vi 1vi w vj 1vj 于是將C改進(jìn)為Cij 顯然改進(jìn)后的回路仍然是H回路且權(quán)值較低 2020 2 5 離散數(shù)學(xué) 36 求下圖的最優(yōu)回路 首先選C v1v2v3v4v5v6v1w C 14 15