Потужність графа

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Граф із потужністю 2. На зображенні показано спосіб видалення ребер, що максимізує описуване відношення: граф розбивається на три частини, при цьому видаляється 4 ребра між цими частинами, що дає відношення 4/(3-1)=2.

Потужність неорієнтованого графа — характеристика графа, що дорівнює найменшому відношенню кількості ребер, видалених із графа, до числа компонент, отриманих внаслідок такого видалення (зменшеного на 1). Цей метод дозволяє визначити зони високої концентрації ребер. Потужність графа подібна до поняття жорсткості графа, яка, проте, визначається через процедуру видалення вершин, а не ребер.

Визначення

Потужність σ(G) неорієнтованого простого графа G=(V,E) можна визначити трьома еквівалентними способами:

  • Нехай Π — множина всіх розбиттів множини V. Для розбиття π∈Π позначимо як ∂π множину ребер, що з'єднують вершини з різних компонент π. Тоді σ(G)=minπ∈Π|∂π||π|−1.
  • Нехай 𝒯 — набір усіх кістякових дерев графа G. Тоді
σ(G)=max⁡{∑T∈𝒯λT : ∀T∈𝒯 λT⩾0;∀e∈E ∑T∋eλT⩽1}.
σ(G)=min⁡{∑e∈Eye : ∀e∈E ye⩾0;∀T∈𝒯 ∑e∈Eye⩾1}.

Складність

Потужність графа можна обчислити за поліноміальний час. Перший поліноміальний алгоритм виявив Каннінгем (1985). Алгоритм для обчислення потужності з найкращою складністю, який належить Трубіну (1993), використовує розклад потоку Голдберга та Рао (1998) і працює за час O(min⁡(m,n2/3)mnlog⁡(n2/m+2)).

Властивості

  • Якщо π={V1,…,Vk} — розбиття, яке максимізує відношення і для i∈{1,…,k}Gi=G/Vi є звуженням графа G на множину Vi, то σ(Gk)⩾σ(G).
  • Теорема Татта — Неша — Вільямса: ⌊σ(G)⌋ є найбільшим числом кістякових дерев, що не перетинаються по ребрах, які можуть міститися в G.
  • На відміну від задачі про розбиття графа, одержувані при обчисленні потужності розбиття не обов'язково збалансовані (тобто майже одного розміру).

Література

Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Потужність_графа&oldid=9736