PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 用induction證明無向圖必有一點為non-cut

看板Prob_Solve (計算數學 Problem Solving)作者eieio (好多目標)時間11年前 (2013/11/03 16:07)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/4 (看更多)

※ 引述《jvvbn0601 (part2)》之銘言： : For an undirected graph G=(V, E) and a vertex v in V, let G\v denote the : subgraph of G obtained by removing v and all the edges incident to v from G. If G is : connected, then G\v can be connected or disconnected. Prove that for any connected graph G, : we can always find a vertex v in G such that G\v is connected. : 目前我的想法是1)沒有迴圈:視為樹，leaf必定是non-cut : 2)有迴圈:有迴圈的話，degree不是最大的應該都可以是non-cut? : 請問一下，我的觀念是否有錯? : 還有如何用數學歸納法證明呢? 有 cycle 也不見得可以從 cycle 拔，例如三個點組成三角形，下面連另外兩個點，變成 "A" 的形狀，中間的兩個點一拔就斷了。我的做法不使用數學歸納法，參考一下。很久沒做題目了，希望沒錯。先在圖中任取一點 v0，然後對所有其他點，計算到達 v0 的最短路徑，直接相連的鄰居就是 1，鄰居的鄰居為 2，以此類推。全部算完之後，隨便挑一個離 v0 最遠的 v，把它拔掉即可。v0 必然仍然和所有的點連通，若有一點 v' 因為拔掉 v 而不再和 v0 相連，那麼 v 必然在 v0 到 v' 的所有路徑上，包括最短路徑，這與 v 是離 v0 最遠的點矛盾，因此 v0 和所有的點連通。任兩點也可經過 v0 互相連通，因此整個圖仍為連通。 -- Just because you deserve this doesn't mean they're gonna give it to you. Sometimes you gotta take what's yours. ── Kenny Ray Carter -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 174.21.233.189