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

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

看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間11年前 (2013/11/03 20:15)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/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? : 請問一下，我的觀念是否有錯? : 還有如何用數學歸納法證明呢? 這命題還不夠強，不是很好證。姑且改成「砍掉之後還是connected graph的點，至少有兩點。」 (1) 圖上只有兩點，顯然成立。 (2) 現在圖上嘗試增加一點，形成connected graph。　　大致上可以分成這些情況：　　x. 新點連著一個、兩個、三個、...的connected graph。　　y. 連接的邊可以是一條、兩條、三條、...。　　比較值得討論的情況就這四種：http://postimg.org/image/rc4ehhkzf/ 　　1. 新點 + connected graph裡面沒被新點連到的那個割點。　 2. 新點 + connected graph裡面那兩個割點。　　3. 兩個connected graph裡面，沒被新點連到的割點，各一個。 4. 被兩條邊以上連到的coneected graph裡面那兩個割點。就證完了 -- 用「有無cycle」、「有無degree = 1的點」來分類，似乎都不是很好證。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 36.225.182.249 ※ 編輯: DJWS 來自: 36.225.182.249 (11/03 20:17)