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

У теорії графів підмножина вершин ${\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.

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

Іншим класом прикладів є вільне дерево T, яке має сепаратор S, що складається з однієї вершини, видалення якої розділяє T на дві (або більше) зв'язні компоненти, кожна з яких має розмір, що не перевищує n/2. Точніше, існує рівно одна або дві вершини, залежно від того, є дерево ^[en] чи ^[en].

Всупереч наведеним прикладам не всі вершинні сепаратори збалансовані, але ця властивість найкорисніша для застосування в інформатиці.

Мінімальні сепаратори

Нехай S — (a, b)-сепаратор, тобто підмножина вершин, що розділяє дві несуміжні вершини a і b. Тоді S є мінімальним (a, b)-сепаратором, якщо ніяка підмножина S не розділяє a і b. Множина S називається мінімальним сепаратором, якщо вона є мінімальним сепаратором для будь-якої пари (a, b) несуміжних вершин. Нижче наведено добре відомий результат, що стосується характеризації мінімальних сепараторів:

Лема. Верховий сепаратор S у G мінімальний тоді і тільки тоді, коли граф ${\displaystyle G-S}$, Отриманий видаленням S із G, має дві зв'язні компоненти ${\displaystyle C_{1}}$ і ${\displaystyle C_{2}}$ такі, що кожна вершина в S зв'язна з деякою вершиною в ${\displaystyle C_{1}}$ і деякою вершиною в ${\displaystyle C_{2}}$.

Мінімальні сепаратори утворюють алгебричну систему: для двох фіксованих вершин a і b даного графу G (a, b)-сепаратор S можна розглядати як попередник іншого (a, b)-сепаратора T, якщо будь-який шлях з a в b потрапляє в S перш, ніж потрапити в T. Строгіше відношення передування визначається так: нехай S і T — два (a, b)-сепаратори в G. Тоді S є попередником T, що позначається як ${\displaystyle S\sqsubseteq _{a,b}^{G}T}$, якщо для будь-якої вершини ${\displaystyle x\in S\setminus T}$ будь-який шлях, що з'єднує x і b, містить вершину з T. З визначення випливає, що відношення передування є передпорядком на множині всіх (a, b)-сепараторів. Більш того, Ескаланте довів, що відношення передування стає , якщо обмежитися множиною мінімальних (a, b)-сепараторів G.

Див. також

• Хордальний граф — граф, у якому будь-який мінімальний сепаратор є клікою.
• Алгебрична зв'язність

Примітки

1. J. Alan George. Nested dissection of a regular finite element mesh // SIAM Journal on Numerical Analysis. — 1973. — Т. 10, вип. 2 (16 червня). — С. 345—363. — DOI:10.1137/0710032.. Замість використання рядків і стовпців графу, Джордж розделяє граф на чотири частини об'єднанням рядків і стовпців як сепаратором.
2. Camille Jordan. Sur les assemblages de lignes // . — 1869. — Т. 70, вип. 2 (16 червня). — С. 185—190.
3. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. — Academic Press, 1980. — .
4. F. Escalante. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. — 1972. — Т. 38. — С. 199—220. — DOI:10.1007/BF02996932.

Література

• Arnold Rosenberg, Lenwood Heath. Graph Separators, with Applications. Springer. — 2002. — 16 червня. — DOI:10.1007/b115747.