Re: [問題] 用induction證明無向圖必有一點為non-cut
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/11/04 11:34)推噓1(1推 0噓 0→)留言1則, 1人參與討論串4/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.
Read the condition more carefully..
You have a connected Graph G, and you want to prove
there is at least a point v in G,
such that G\v is connected..
1. Because G is connected, we can always generate a
Minimum-spanning tree (MST) for G.
2. Pick one leaf in MST, we call it v in G.
3. Now, the remaining G\v is still connected. Done.
You need to work on some finer detail, but I think this works.
--
一簫一劍平生意
負盡狂名十五年
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.125.20.24
推
11/04 16:13, , 1F
11/04 16:13, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
