Вершинный сепаратор (теория графов)

---

В теории графов подмножество вершин ${\displaystyle S\subset V}$ называется вершинным сепаратором для несмежных вершин ${\displaystyle a}$ и ${\displaystyle b}$, если удаление ${\displaystyle S}$ из графа разделяет ${\displaystyle a}$ и ${\displaystyle b}$ в две компоненты связности.

Предположим, что задана решётка с r строками и c столбцами, тогда полное число n вершин равно r*c. Например, на рисунке, r = 5, c = 8 и n = 40. Если r нечётно, существует одна центральная строка, в противном случае существуют две строки, одинаково близких к центру. Таким же образом, если c нечётно, существует один центральный столбец, в противном случае существуют два столбца, одинаково близких к центру. Выбрав в качестве S одну из этих строк или столбцов, и удалив S из графа, получим разбиение графа на два меньших связных подграфа A и B, каждый из которых содержит максимум n/2 вершин. Если r ≤ c (как на иллюстрации), то выбор центрального столбца даст сепаратор S с r ≤ √n вершинами, и, таким же образом, если c ≤ r, выбор центральной строки даст сепаратор с максимум √n вершинами. Таким образом, любой граф-решётка имеет сепаратор S с размером, не превосходящим √n, удаление которой разделяет граф на две связные компоненты, каждая с размером, не превосходящим n/2^[1].

В качестве другого класса примеров можно использовать свободное дерево T, которое имеет сепаратор S, состоящий из одной вершины, удаление которой разделяет T на две (или более) связные компоненты, каждая из которых имеет размер, не превосходящий n/2. Точнее, существует в точности одна или две вершины, в зависимости от того, является ли дерево центрированным^[англ.] или бицентрированным^{[англ.][2]}.

Вопреки приведённым примерам не все вершинные сепараторы сбалансированы, но это свойство наиболее полезно для приложений в информатике.

Пусть S — (a,b)-сепаратор, то есть подмножество вершин, разделяющее две несмежные вершины a и b. Тогда S является минимальным (a,b)-сепаратором, если никакое подмножество S не разделяет a и b. Множество S называется минимальным сепаратором, если оно является минимальным сепаратором для какой-либо пары (a,b) несмежных вершин. Ниже приведён хорошо известный результат, касающийся характеризации минимальных сепараторов^[3]:

---