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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории графов подмножество вершин S \subset V называется вершинным сепаратором для несмежных вершин 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 с r ≤ √n вершинами, и, таким же образом, если c ≤ r, выбор центральной строки даст сепаратор с максимум √n вершинами. Таким образом, любой граф-решётка имеет сепаратор S с размером, не превосходящим √n, удаление которой разделяет граф на две связные компоненты, каждая с размером, не превосходящим n/2.[1]

На левом дереве одна центральная вершина. На правом дереве две центральные вершины. Числа, показанные на рисунке у вершин, показывают эксцентриситет

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

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

Минимальные сепараторы[править | править вики-текст]

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

Лемма. Вершинный сепаратор S в G минимален тогда и только тогда, когда граф G-S, полученный удалением S из G, имеет две связные компоненты C_1 и C_2, такие что каждая вершина в S связна с некоторой вершиной в C_1 и некоторой вершиной в C_2.

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

Смотрите также[править | править вики-текст]

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

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

References[править | править вики-текст]

  • F. Escalante Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1972. — Т. 38. — С. 199–220. — DOI:10.1007/BF02996932
  • J. Alan George, Nested dissection of a regular finite element mesh // SIAM Journal on Numerical Analysis. — 1973. — В. 2. — Т. 10. — С. 345–363. — DOI:10.1137/0710032.
  • Martin Charles Golumbic Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — ISBN 0-12-289260-7.
  • Camille Jordan Sur les assemblages de lignes (фр.) // Journal für die reine und angewandte Mathematik. — 1869. — В. 2. — Т. 70. — С. 185–190.
  • Arnold Rosenberg, Lenwood Heath Graph Separators, with Applications. Springer.. — 2002. — DOI:10.1007/b115747