看板 [ Prob_Solve ]
討論串[問題] 用induction證明無向圖必有一點為non-cut
共 4 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 用induction證明無向圖必有一點為non-cut
推噓4(4推 0噓 4→)留言8則，0人參與, 最新作者jvvbn0601 (part2)時間11年前 (2013/10/30 21:14), 編輯資訊
3
0
0
內容預覽:
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.
(還有178個字)
#2
Re: [問題] 用induction證明無向圖必有一點為non-cut
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者eieio (好多目標)時間11年前 (2013/11/03 16:07), 編輯資訊
0
0
0
內容預覽:
有 cycle 也不見得可以從 cycle 拔，例如三個點組成三角形，下面連另外兩. 個點，變成 "A" 的形狀，中間的兩個點一拔就斷了。. 我的做法不使用數學歸納法，參考一下。很久沒做題目了，希望沒錯。. 先在圖中任取一點 v0，然後對所有其他點，計算到達 v0 的最短路徑，直接. 相連的鄰居就是
(還有270個字)
#3
Re: [問題] 用induction證明無向圖必有一點為non-cut
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者DJWS (...)時間11年前 (2013/11/03 20:15), 編輯資訊
0
0
1
內容預覽:
這命題還不夠強，不是很好證。. 姑且改成「砍掉之後還是connected graph的點，至少有兩點。」. (1) 圖上只有兩點，顯然成立。. (2) 現在圖上嘗試增加一點，形成connected graph。. 大致上可以分成這些情況：. x. 新點連著一個、兩個、三個、...的connected
(還有246個字)
#4
Re: [問題] 用induction證明無向圖必有一點為non-cut
推噓1(1推 0噓 0→)留言1則，0人參與, 最新作者Leon (Achilles)時間11年前 (2013/11/04 11:34), 編輯資訊
0
0
0
內容預覽:
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 connecte
(還有184個字)
首頁
上一頁
1
下一頁
尾頁