計(jì)算機(jī)問(wèn)題求解-2021-09-13-圖中的通路與連通

計(jì)算機(jī)問(wèn)題求解

–

論題3-3

-圖中的通路與連通2021年09月13日PartI圖的連通度問(wèn)題1：如果一個(gè)通信/交通網(wǎng)絡(luò)中一個(gè)結(jié)點(diǎn)失效了，其它結(jié)點(diǎn)之間還能正?；ネ▎?？我們也可以換個(gè)角度提出問(wèn)題：一個(gè)通信/交通網(wǎng)絡(luò)中哪些結(jié)點(diǎn)對(duì)維護(hù)網(wǎng)絡(luò)連通最關(guān)鍵？“連通”與“連通”可能不一樣問(wèn)題2：利用下面的圖解釋一下bridge,cut-vertex的概念。順便問(wèn)一句：兩者有什么關(guān)聯(lián)？問(wèn)題3：割邊關(guān)聯(lián)的頂點(diǎn)是否一定是割點(diǎn)？Theorem5.1

Let

v

beavertexincidentwithabridgeinaconnectedgraphG.Then

v

isacut-vertexofGifandonlyif

deg

v≥2.為什么只要degv不小于2，v就一定是割點(diǎn)？uvabridge假如degv>1wv如果不是割點(diǎn)會(huì)導(dǎo)致什么矛盾？割邊在回路上?!問(wèn)題4：從本質(zhì)上看，你認(rèn)為cut-vertex這個(gè)詞中的“cut”，“割斷”的什么？Theorem5.3

Letvbeacut-vertexinaconnectedgraphGandletuandwbeverticesindistinctcomponentsofG?v.Thenvliesoneveryu?wpathinG.Corollary5.4

Avertex

v

ofaconnectedgraphGisacut-vertexofGifandonlyifthereexistverticesuandwdistinctfrom

v

suchthat

v

liesoneveryu

?

wpathofG.“割點(diǎn)”的核心特征：它的刪除一定“切斷”某兩點(diǎn)之間一切通路。問(wèn)題5：是否有可能一個(gè)連通圖中所有的點(diǎn)都是割點(diǎn)？你還記得嗎：樹(shù)中的邊均為bridge!你能拿上面的圖做例子解釋一下嗎？你能“順便”說(shuō)明為什么一個(gè)連通圖中也不可能只有一個(gè)非割點(diǎn)嗎？你還記得什么是圖的“直徑”嗎？問(wèn)題6：割點(diǎn)“割斷”某兩點(diǎn)之間所有通路，你能根據(jù)這一點(diǎn)解釋為什么一個(gè)圖中，如果任何兩個(gè)頂點(diǎn)一定位于同一個(gè)回路上，則圖中不可能有割點(diǎn)嗎？其逆命題也成立：Theorem5.7

Agraphoforderatleast

3

isnonseparableifandonlyifeverytwoverticeslieonacommoncycle.問(wèn)題7：為什么可以將一個(gè)連通圖中所有的block看作其邊集在某種等價(jià)關(guān)系下的分劃？block:不含割點(diǎn)的極大子圖euvfg能否證明任何兩個(gè)block不可能有公共邊？若n>2，任何兩點(diǎn)之間至少存在兩條點(diǎn)不相交的通路。一個(gè)連通圖中的任意兩個(gè)不同的block最多只會(huì)有一個(gè)公共定點(diǎn)，而且如果有，這個(gè)頂點(diǎn)一定是圖中的割點(diǎn)。uvwB1B2e1e2矛盾：e1和e2應(yīng)該在G的同一block中B1B2e1e2vP如果v不是割點(diǎn)，就一定存在P，那就會(huì)怎樣呢?問(wèn)題8：你能否利用以上的圖解釋上述結(jié)論？問(wèn)題9：兩個(gè)block的“分界點(diǎn)”一定是割點(diǎn)，這能否啟發(fā)你想出一個(gè)劃分無(wú)向圖中block的算法？基于DFS的Block算法：基本思想vwAncestorsofvSubtreerootedatwBackedgev

是割點(diǎn)當(dāng)且僅當(dāng)沒(méi)有任何backedges會(huì)將以w根的子樹(shù)中的任一頂點(diǎn)連接到v的任何一個(gè)祖先頂點(diǎn)。如果我們能判定v是從當(dāng)前考慮的分支的根上朔最遠(yuǎn)的割點(diǎn)，則可以分離出一個(gè)block。順便問(wèn)一句：“分離”發(fā)生在什么時(shí)刻？注意：無(wú)向圖中不可能有cross-edge分離block算法的實(shí)現(xiàn)幾個(gè)關(guān)鍵問(wèn)題：為什么DFS過(guò)程適合解block分離的問(wèn)題？DFS樹(shù)和原來(lái)的圖是什么關(guān)系？如何判斷一個(gè)節(jié)點(diǎn)是割點(diǎn)？DFS樹(shù)中某個(gè)子樹(shù)的根是割點(diǎn)有什么特征？在DFS過(guò)程中，保存哪些數(shù)據(jù)能幫我們判斷上述特征？你能想象用DFS方法分離出來(lái)的block中的邊被識(shí)別的順序嗎？用什么數(shù)據(jù)結(jié)構(gòu)利于實(shí)現(xiàn)分離過(guò)程？Block算法（部分）示意圖問(wèn)題10：只考慮有割點(diǎn)或者是unseparable來(lái)區(qū)分連通圖的連通“牢度”，似乎還太粗略了一些，我們是如何進(jìn)行更細(xì)致的度量的呢？問(wèn)題11：Vertex-cut和cut-vertex有什么異同？它是如何被用來(lái)定義連通的“牢度”的？又怎樣將這個(gè)概念拓展到edge的？你能否利用上面的圖直觀(guān)地說(shuō)說(shuō)，和三者之間的大小關(guān)系？

Whitney定理關(guān)鍵是證明第一個(gè)不等式，且主要考慮非完全的連通圖（n3）。Let

X

beaminimumedge-cutof

G.Then|X|=

λ(G)≤

n

?2.Necessarily,

G

?

X

containsexactlytwocomponents

G1

and

G2.Supposethattheorderof

G1

is

k.Thustheorderof

G2

is

n

?

k,where

k

≥1and

n

?

k

≥1.Consequently,everyedgein

X

joinsavertexof

G1

andavertexof

G2.uv最小邊割集X中的邊加入頂點(diǎn)集U的點(diǎn)顯然，U是點(diǎn)數(shù)不超過(guò)|X|的點(diǎn)割集G1G2為什么一定存在不相鄰的點(diǎn)對(duì)u,v？PartII歐拉圖與哈密爾頓圖現(xiàn)在,我們換個(gè)話(huà)題:談?wù)剝煞N包含特別通路的特殊的圖歐拉圖：存在歐拉回路，經(jīng)過(guò)每條邊恰好1次。哈密爾頓圖：存在哈密爾頓回路，經(jīng)過(guò)每個(gè)點(diǎn)恰好1次。從七橋問(wèn)題到歐拉圖問(wèn)題12：為什么七橋問(wèn)題“無(wú)解”？Theorem6.1

AnontrivialconnectedgraphGisEulerianifandonlyifeveryvertexofGhasevendegree.充分條件的證明u(v)如果所有頂點(diǎn)均為偶數(shù)次，圖中最長(zhǎng)的簡(jiǎn)單通路一定是回路。xyCC’假設(shè)那個(gè)最長(zhǎng)的回路不包括圖中所有的邊，一定會(huì)導(dǎo)致矛盾：它就不是最長(zhǎng)。刪除C后得到的某個(gè)分支。如果用大家更熟悉的證明語(yǔ)言描述：數(shù)學(xué)歸納法順便問(wèn)一句：你能聯(lián)想到算法嗎？如何“畫(huà)”出一個(gè)歐拉回路？即使知道G是歐拉圖，即理論上說(shuō)從任何一點(diǎn)開(kāi)始總是有可能“一筆畫(huà)”出整個(gè)圖G，但并不意味著你可以“隨手畫(huà)”。那“成敗”的關(guān)鍵在哪里呢？不能“斷”了返回源點(diǎn)的去路,也就是說(shuō)還有正度數(shù)的點(diǎn)必須連通。！算法到“無(wú)路可走時(shí)結(jié)束，此時(shí)形成的路徑一定是歐拉回路。左邊的圖示意圖論中常用的證明技巧：如果結(jié)束時(shí)終點(diǎn)不是v0/vn,則從原圖中刪除路徑上的邊得到的不是空?qǐng)D（為什么？）假設(shè)em+1是最后一次離開(kāi)S的邊,…..GmS中的點(diǎn)均有正度數(shù)問(wèn)題13：沒(méi)有歐拉回路但包含歐拉通路的圖的充分必要條件應(yīng)該是什么？順便問(wèn)一句，如果連歐拉通路也沒(méi)有，你能對(duì)這樣的圖說(shuō)寫(xiě)什么呢？從歐拉圖到中國(guó)郵遞員問(wèn)題GG’哈密爾頓圖：判定條件問(wèn)題14：充分必要與充分+必要，差別有多大？是/非界線(xiàn)明確“灰色”地帶一個(gè)必要條件Theorem6.5

IfGisaHamiltoniangraph,thenforeverynonemptypropersetSofverticesofG,G哈密爾頓回路C分支i分支i+1一定屬于S的頂點(diǎn)問(wèn)題15：你能參照左邊的圖解釋一下上述結(jié)論嗎？必要條件的應(yīng)用問(wèn)題16：是否哈密爾頓圖與圖的稠密程度應(yīng)該沒(méi)有直接關(guān)系，但完全圖必定是哈密爾頓圖，這點(diǎn)對(duì)你有什么啟發(fā)嗎？Theorem6.6

Let

G

beagraphoforder

n

≥3.

If

foreachpairu,

v

ofnonadjacentverticesofG,thenGisHamiltonian.如果圖G滿(mǎn)足上述條件，卻不是哈密爾頓圖，我們總可以通過(guò)在G中不相鄰的定點(diǎn)之間加邊，得到滿(mǎn)足以下條件的圖H:H仍然不是哈密爾頓圖；在H的任一不相鄰頂點(diǎn)對(duì)之間再加一條邊就使其成為哈密爾頓圖；顯然H仍滿(mǎn)足以上不等式。后面的任務(wù)就是在H中推出矛盾。你試試！灰色地帶Petersen圖滿(mǎn)足必要條件，但不滿(mǎn)足充分條件。

Petersen圖不是哈密爾頓圖?！芭卸ā钡碾y度差別就這么大，更別說(shuō)相關(guān)問(wèn)題：中國(guó)郵遞員問(wèn)題和旅行推銷(xiāo)商問(wèn)題的差別了。一個(gè)令人困惑的“科學(xué)問(wèn)題”SomeproblemshaveinsightslikeEuler’s,andothersseemtorequireanexhaustivesearch.Whatmakesthedifference?Whatkindsofstrategiescanweusetoskiporsimplifythissearch,andforwhichproblemsdotheywork?Ahostofproblems—findingHamiltonianpaths,coloringgraphs,satisfyingformulas,andbalancingnumbers—areallequallyhard.Ifwecouldsolveanyofthemefficientl