Re: [問題] Complete Graph Kn has no vertex cut?

[f54512 (這不是柏良 這不是柏良)]

※ 引述《f54512 (這不是柏良 這不是柏良)》之銘言：
※ 引述《anfranion (安弗尼恩)》之銘言：
: 如題，請問Kn的vertex cut為什麼不是拿掉的那n-1個點呢？
: (從投影片33頁來的)
: 問題好多 感謝助教+板上的學長姐/同學的回答:D!
同學你好 我可能有點誤會你的問題^^|||

這邊只是解釋一下為什麼Kn的vertex cut會有n-1個點

connectivity可以理解成至少要拿掉多少個點可以使該graph變成disconnected

由於Kn是個complete graph 所以任兩點都有edge連接

要使該graph成為disconnected就只能將n-1個點都拿掉 只剩單一一個點

歡迎同學提出問題 大家可以多多討論^^

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.94.1
推 anfranion:其實我只是不懂那句which has no vertex cut
→ anfranion:因為整句的意思應該是有  可是這句又說沒有囧?
→ anfranion:請助教幫忙解答了  謝謝~
推 anfranion:另外請問一下  if and only if就是<==>的意思嗎?
不好意思 助教之前解釋有問題

connectivity是定義成最小的vertex cut的size

但是針對Kn而言 vertex cut是不存在的

因為拿掉n-1個點之後 會變成一個isolated vertex並非disconnected

但是為了方便將Kn的connectivity定為n-1

http://en.wikipedia.org/wiki/Connected_graph

另外，if and only if就是<==>的意思

謝謝同學提出來討論^^

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.135.94.1
推 anfranion:原來如此  謝謝助教！