雖然這篇被歸類在網路流量問題之中,但是為了銜接下一篇最大流量-最小割定理,我會暫時離題並討論一下什麼是「割 (cut)」。一般討論割的目的是為了瞭解一張圖 (graph) 是否足夠穩固,或至少要移除多少節點或邊才能使整張圖分為兩個連通塊 (component)。可以想像要是在一個公路的路網,被摧毀幾條公路就會使兩地之間無法溝通。顯然這是一個很重要的問題
本篇會來介紹點割 (vertex cut)、邊割 (edge cut) 與連通性 (connectivity)。最後會來介紹 Menger 定理,說明點割、邊割與路徑乃至於整張圖的關係。Menger 定理在圖論是個極為重要的存在,因為它的效力與許多不同的定理等價,像是 Hall 定理、 Kőnig 定理等都能使用 Menger 定理互相推出來
點割 Vertex Cut
定義
在一張圖 $G$ 中,若存在集合 $S\subseteq V(G)$ 使 $G-S$ 有多於一個連通塊,則 $S$ 是一個點割 (vertex cut)
給定 $x, y\in V(G)$,若存在集合 $S\subseteq V(G) - {x, y}$ 使 $G-S$ 沒有從 $x$ 到 $y$ 的路徑,則 $S$ 被稱為 $x, y$ 點割 ($x, y$-cut)
$\kappa(x, y)$ 為最小 $S$ 的元素個數,即最小 $x, y$-cut 的大小