[問題] 用induction證明無向圖必有一點為non-cut
看板Prob_Solve (計算數學 Problem Solving)作者jvvbn0601 (part2)時間11年前 (2013/10/30 21:14)推噓4(4推 0噓 4→)留言8則, 3人參與討論串1/4 (看更多)
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?
請問一下，我的觀念是否有錯?
還有如何用數學歸納法證明呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.160.42.4
推
10/30 23:40, , 1F
10/30 23:40, 1F
推
10/31 06:27, , 2F
10/31 06:27, 2F
→
10/31 06:28, , 3F
10/31 06:28, 3F
推
11/03 17:01, , 4F
11/03 17:01, 4F
→
11/03 17:02, , 5F
11/03 17:02, 5F
推
11/04 09:27, , 6F
11/04 09:27, 6F
→
11/04 09:27, , 7F
11/04 09:27, 7F
→
11/04 09:33, , 8F
11/04 09:33, 8F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
