Разделитель вершин - Vertex separator

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

Примеры

Разделитель для сеточного графа.

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

Слева центрированное дерево, справа двухцентровое. Цифры показывают каждый узел эксцентриситет.

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

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

Минимальные разделители

Позволять S быть (а, б)-сепаратор, то есть подмножество вершин, разделяющее две несмежные вершины а и б. потом S это минимальный (a, b) -сепаратор если нет подходящего подмножества S отделяет а и б. В более общем смысле, S называется минимальный разделитель если это минимальный разделитель для некоторой пары (а, б) несмежных вершин. Обратите внимание, что это отличается от минимальное разделяющее множество который говорит, что нет надлежащего S минимальный (u, v)-сепаратор для любой пары вершин (u, v). Следующее - хорошо известный результат, характеризующий минимальные разделители:^[3]

Лемма. Разделитель вершин S в грамм минимален тогда и только тогда, когда граф ${\displaystyle G-S}$, полученный удалением S из грамм, имеет две компоненты связности ${\displaystyle C_{1}}$ и ${\displaystyle C_{2}}$ такая, что каждая вершина в S оба смежны с некоторой вершиной в ${\displaystyle C_{1}}$ и в какую-то вершину в ${\displaystyle C_{2}}$.

Минимальные "(a, b)" - разделители также образуют алгебраическая структура: Для двух фиксированных вершин а и б данного графа грамм, (а, б)-разделитель S можно рассматривать как предшественник другого (a, b) -сепаратора Т, если каждый путь от а к б встречает S до встречи Т. Более строго, отношение предшественника определяется следующим образом: Пусть S и Т быть двумя (а, б)-сепараторы в 'G'. потом S является предшественником Т, в символах ${\displaystyle S\sqsubseteq _{a,b}^{G}T}$, если для каждого ${\displaystyle x\in S\setminus T}$, каждый путь, соединяющий Икс к б встречает Т. Из определения следует, что отношение предшественника дает Предварительный заказ на множестве всех (а, б)-сепараторы. Более того, Эскаланте (1972) доказал, что отношение предшественника порождает полная решетка когда ограничен набором минимальный (а, б)-сепараторы в грамм.

Смотрите также

• Хордовый граф, граф, в котором каждый минимальный разделитель является клика.
• k-вершинно-связный граф

Примечания

1. Джордж (1973). Вместо использования строки или столбца сеточного графа Джордж разделяет граф на четыре части, используя объединение строки и столбца в качестве разделителя.
2. Иордания (1869)
3. Голумбик (1980).

Рекомендации

• Escalante, F. (1972). «Schnittverbände in Graphen». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 38: 199–220. Дои:10.1007 / BF02996932.
• Джордж, Дж. Алан (1973), «Вложенное рассечение регулярной сетки конечных элементов», Журнал SIAM по численному анализу, 10 (2): 345–363, Дои:10.1137/0710032, JSTOR  2156361.
• Голумбик, Мартин Чарльз (1980), Алгоритмическая теория графов и совершенные графы, Academic Press, ISBN  0-12-289260-7.
• Иордания, Камилла (1869). "Sur les Assemblages de lignes". Журнал für die reine und angewandte Mathematik (На французском). 70 (2): 185–190.
• Розенберг, Арнольд; Хит, Ленвуд (2002). Разделители графиков с приложениями. Springer. Дои:10.1007 / b115747.