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

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

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

Визначення

[ред. | ред. код]

Потужність неорієнтованого простого графа можна визначити трьома еквівалентними способами:

  • Нехай  — множина всіх розбиттів множини . Для розбиття позначимо як множину ребер, що з'єднують вершини з різних компонент . Тоді .
  • Нехай  — набір усіх кістякових дерев графа . Тоді

Складність

[ред. | ред. код]

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

Властивості

[ред. | ред. код]
  • Якщо  — розбиття, яке максимізує відношення і для є звуженням графа на множину , то .
  • Теорема Татта — Неша — Вільямса: є найбільшим числом кістякових дерев, що не перетинаються по ребрах, які можуть міститися в .
  • На відміну від задачі про розбиття графа, одержувані при обчисленні потужності розбиття не обов'язково збалансовані (тобто майже одного розміру).

Література

[ред. | ред. код]