Re: [理工] [離散]-圖論
※ 引述《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
推
02/22 13:58, , 1F
02/22 13:58, 1F
推
02/22 14:45, , 2F
02/22 14:45, 2F
→
02/22 15:00, , 3F
02/22 15:00, 3F
討論串 (同標題文章)