推 polomoss:謝，所以如果用命題→就對了嗎? 02/22 13:58
推 ie925155:感謝你 02/22 14:45
→ FRAXIS:頂點聯通度 <= 最小分支度 這是一個定理 可以推出你說的=> 02/22 15:00
※ 引述《polomoss (小澤)》之銘言：
: The connectivity or vertex connectivity κ(G) is the size of a smallest
: vertex cut. A graph is called k-connected or k-vertex-connected if its vertex
: connectivity is k or greater.
:
: 拿掉k個點才使圖不連通 = 每個點的degree至少k (這樣有錯嗎?)
如果一個圖是k-vertex-connected，那每個頂點的degree至少是k沒錯。
因為如果有某個頂點的degree < k，那麼我們可以把該頂點的鄰居都刪
除，就可以讓此圖型不連通。
如果一個圖每個頂點的degree至少是k，不代表是k連通，所以你寫=的關
係是不正確的。
反例，先建造兩個Kn(完全圖)，其中每個點的degree都是n-1，然後增加
n/2個頂點，分別連向這兩個Kn中的所有頂點，因此這n/2個頂點的degree
至少也是n。不過這個圖的vertex-connectivity只有n/2（把新增加的n/2
個頂點拿掉，剩下的只是兩個不相連的Kn）。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50