離散數學筆記 — 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