※ 引述《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