頂點分離器

不要將其與剪切頂點混淆。

在圖理論中，頂點子集對於非附屬頂點A和B，如果從圖中刪除S和B分隔為不同的連接組件，則是非附屬頂點A和B的頂點分離器（或頂點分離集）。

例子

網格圖的分離器。

考慮帶有R行和C列的網格圖；頂點的總數為r × c 。例如，在圖中， r = 5 ， c = 8和n = 40 。如果r奇怪，則有一個中央行，否則有兩個行同樣靠近中心的行；同樣，如果C是奇數的，則有一個中央列，否則有兩個列同樣靠近中心。選擇s是這些中央行或列中的任何一個，然後從圖中刪除s ，將圖表分為兩個較小的連接子圖A和B ，每個子圖最多都有 n ⁄ 2個頂點。如果r≤c （如圖所示），則選擇一個中央列將使一個分離器S具有頂點，同樣，如果c≤r ，那麼選擇中心行最多會給一個分離器頂點。因此，每個網格圖最多都有一個大小的分離器將其拆分為兩個連接的組件，每個分區最多都有n ⁄ 2 。

在左側，一棵居中的樹，右邊是一棵雙層。數字顯示每個節點的偏心率。

為了給出另一類的示例，每個自由樹都有一個由一個頂點組成的分離器s ，將t的t分區t拆下為兩個或多個連接的組件，每個分區最多均具有n ⁄ 2 。更確切地說，總是有一個或恰好是兩個頂點，這相當於這樣一個分離器，具體取決於樹是中心還是雙層。

與這些示例相反，並非所有頂點分離器都平衡，但是該屬性對於計算機科學中的應用最有用，例如平面分離器定理。

最小的分離器

令s為（ a ， b ） - 分離符，即一個頂點子集，該子集將兩個非附屬頂點a和b分開。然後s是最小（ a ， b ） -分離器，如果沒有適當的子集分離a和b 。更一般而言，如果它是某個非附屬頂點（ a ， b ）的最小分離器，則稱為最小分離器。請注意，這與最小的分離集不同，該集合表明，對於任何一對頂點（ U ， V ），沒有適當的S子集是最小（ U ， V ）分隔符。以下是表徵最小分離器的眾所周知的結果：

引理。當且僅當通過從G中刪除S獲得的圖G – S時， G中的頂點分離器S是最小的到C 2中的一些頂點。

最小（ a ， b ）分離器還形成一個代數結構：對於給定圖G的兩個固定頂點A和B - 分離器t ，如果從A到B的每條路徑都會在t遇到t之前相遇。更嚴格的是，前身關係定義為如下：令S和T為G中的兩個（ a ， b ）分離器。然後s是t的前身，在符號中 ，如果對於每個x∈S \ t ，則將x連接到b的每個路徑符合t 。從以下定義來看，前身關係在所有（ a ， b ）分離符的集合中產生預訂。此外， Escalante（1972）證明，當限制在G中的最小（ a ， b ）分離師的集合時，前身的關係產生了一個完整的晶格。

也可以看看