離散數學筆記 — vertex cut

1. 在圖 G 中，如果去掉一點 v，剩下的圖 G 產生比圖 G 更多 connected component，那麼這個點就是 cut vertex。但是在 complete graph裡，找不到這麼一個點 v 可以生成更多的 connected component，所以 complete graph 並沒有 cut vertex。( e.x. K4 去掉任一點只會變成 K3，它還是只有一個連通圖 )

2. Vertex cut 則是由點組成的一個集合，去掉這些點，剩下的圖 G 就會變成 disconnected。

3. Vertex connectivity，即 k(G)，則是指最少要去掉幾個點，也就是 vertex cut 的最小數目，剩下的圖 G 會變成 disconnetced，或是變成只剩單獨一點。( 因為 vertex cut 可能有包含很多點，但其實用不著那麼多個點就能讓剩下的圖 G 變成 disconnected，所以另外定義 k(G) )

e.x.  (1) k(K4)=3 —因為 complete graph 沒有 vertex cut，所以 k(Kn) = n-1，讓它變成單獨一點
        (2) k(C4)=2 —拿掉對角線兩個點，可另外推得當n≧3，k(Cn)=2
        (3) k(W4)=3 —拿掉中間和對角線兩個點
        (4) k(K2,3)=2 —拿掉其中一邊的所有點，讓另一邊的點彼此連不起來，可另外推得 k(Km,n)=min(m,n)
        (5) k(Q3)=3 —拿掉底部正方形對角線兩點後，再拿掉上層另外一邊的對角線其中一點，可另外推得 k(Qn)=n