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

В теории графов подмножество вершин - это разделитель вершин (или разделение вершин , разделяющее множество ) для несмежных вершин, и если удаление из графа разделяет и на отдельные компоненты связности .${\ Displaystyle S \ подмножество 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) несмежных вершин. Обратите внимание, что это отличается от минимального разделяющего множества, в котором говорится, что никакое собственное подмножество S не является минимальным (u, v) -сепаратором для любой пары вершин(u, v). Следующее - хорошо известный результат, характеризующий минимальные разделители: ^[3]

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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