В теории графов подмножество вершин является разделителем вершин (или срезом вершин , разделяющим множество ) для несмежных вершин a и b , если удаление S из графа разделяет a и b на различные связные компоненты .
Рассмотрим граф сетки с r строками и c столбцами; общее число вершин n равно r × c . Например, на иллюстрации r = 5 , c = 8 и n = 40. Если r нечетно, то есть одна центральная строка, а в противном случае есть две строки, одинаково близкие к центру; аналогично, если c нечетно, то есть один центральный столбец, а в противном случае есть два столбца, одинаково близкие к центру. Выбор S в качестве любой из этих центральных строк или столбцов и удаление S из графа разбивает граф на два меньших связанных подграфа A и B , каждый из которых имеет не более n ⁄ 2 вершин. Если r ≤ c (как на иллюстрации), то выбор центрального столбца даст разделитель S с вершинами, и аналогично, если c ≤ r , то выбор центральной строки даст разделитель с не более чем вершинами. Таким образом, каждый граф сетки имеет сепаратор S размера не более, удаление которого разбивает его на два связных компонента, каждый из которых имеет размер не более n ⁄ 2 . [1]
Чтобы привести другой класс примеров, каждое свободное дерево T имеет сепаратор S, состоящий из одной вершины, удаление которой разбивает T на два или более связанных компонента, каждый размером не более n ⁄ 2 . Точнее, всегда есть ровно одна или ровно две вершины, которые составляют такой сепаратор, в зависимости от того, является ли дерево центрированным или бицентрированным . [2]
В отличие от этих примеров, не все разделители вершин сбалансированы , но это свойство наиболее полезно для приложений в информатике, таких как теорема о плоском разделителе .
Пусть S будет ( a , b ) -разделителем, то есть подмножеством вершин, которое разделяет две несмежные вершины a и b . Тогда S является минимальным ( a , b ) -разделителем , если никакое собственное подмножество S не разделяет a и b . В более общем смысле, S называется минимальным разделителем , если он является минимальным разделителем для некоторой пары ( a , b ) несмежных вершин. Обратите внимание, что это отличается от минимального разделяющего множества , которое гласит, что никакое собственное подмножество S не является минимальным ( u , v ) -разделителем для любой пары вершин ( u , v ) . Ниже приведен хорошо известный результат, характеризующий минимальные разделители: [3]
Лемма. Разделитель вершин S в G минимален тогда и только тогда, когда граф G – S , полученный удалением S из G , имеет две связные компоненты C 1 и C 2 такие, что каждая вершина в S одновременно смежна с некоторой вершиной в C 1 и с некоторой вершиной в C 2 .
Минимальные ( a , b ) -разделители также образуют алгебраическую структуру : для двух фиксированных вершин a и b данного графа G , ( a , b ) -разделитель S можно рассматривать как предшественника другого ( a , b ) -разделителя T , если каждый путь из a в b встречает S до того, как он встречает T. Более строго, отношение предшественника определяется следующим образом: Пусть S и T — два ( a , b ) -разделителя в G. Тогда S является предшественником T , в символах , если для каждого x ∈ S \ T , каждый путь, соединяющий x с b, встречает T. Из определения следует, что отношение предшественника дает предпорядок на множестве всех ( a , b ) -разделителей. Кроме того, Эскаланте (1972) доказал, что отношение предшественника приводит к полной решетке при ограничении множеством минимальных ( a , b ) -разделителей в G.
