頂點Biconnected和邊雙連通誤解

-1

如果沒有頂點的移除斷開圖連接，則連通圖是頂點雙連通的。如果沒有移除切斷圖的邊，則連通圖是邊雙連通的。爲以下語句給出每個證明或反例：頂點Biconnected和邊雙連通誤解

（a）頂點雙連通圖是邊雙連通的。（b）邊雙連通圖是頂點雙連通的。

對於A）我的嘗試是應該是這樣，因爲我沒有看到去除頂點如何影響邊的雙連接。對於B）我的嘗試是NO，因爲如果我們有一個橋，連接兩個圖，刪除該邊將不再具有圖頂點雙連通。

也許我完全錯了，任何援助將不勝感激。

來源

2013-04-20 user2302617

簡單[反例]（https://www.math.umass.edu/~tevelev/zuz.png）（b） – 2013-04-20 17:18:30

@EgorSkriptunoff是我的（a）對不對？ – user2302617 2013-04-20 17:23:23

@ user2302617您沒有提供（a）的證據。你提供了直覺，這是教育的一個重要組成部分，但在正式的背景下無關緊要。 – 2013-04-20 17:33:21

a）證明：通過相互矛盾。令G =（V，E）爲頂點雙連通。假設它不是邊緣雙連通的。那麼存在一個邊e = {v，w}，我們可以去除，使得G'=（V，E \ {e}）被斷開。但是，我們也可以從G中移除v或w，並斷開圖形（因爲移除邊的任一端點也會移除該邊），這與G是頂點雙連通相矛盾;因此G也必須是邊連通的。

來源

2013-04-20 20:25:02

我從視覺圖中學得更好，我很難跟隨你。 – user2302617 2013-04-20 20:28:53

不幸的是，可視化並不能幫助你學會如何證明一些東西。它只能幫助你理解證據背後的直覺。這個背後的想法是：如果我可以通過刪除一條邊來斷開圖，我也可以通過刪除其中一條邊所在的頂點來斷開圖。所以這證明'不是頂點雙連通=>頂點雙連通'，這是你想要證明的東西的對立面。 – 2013-04-20 20:35:50

你真的不應該接受你不明白的答案;如果事情不清楚，最好在評論中要求澄清。 – 2013-04-20 20:42:06

頂點Biconnected和邊雙連通誤解

回答

相關問題