k-реберно-зв'язний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії графів, граф k-реберно-зв'язний, якщо він залишається зв'язним по видаленню менше ніж k ребер.

Формальне визначення[ред.ред. код]

Нехай G = (E,V) довільний граф. Якщо G' = (E \ X,V) є зв'язним для всіх X ⊆ E де |X| < k, тоді G — k-реберно-зв'язний.

Зв'язок з найменшим степенем вершини[ред.ред. код]

Найменший степінь вершини дає трівіальну верхню межу реберної зв'язності. Тобто, якщо граф G = (E,V) є k-реберно-зв'язним, тоді необхідно, щоб k ≤ δ(G), де δ(G) це найменший степінь будь-якої вершини v ∈ V. Очевидно, що видалення всіх ребер інцидентних вершині v, від'єднає v від графа.

Обчислення[ред.ред. код]

Існує алгоритм поліноміального часу для визначення найбільшого k для якого граф G є k-реберно-зв'язним. Простий алгоритм, для кожної пари (u,v), буде визначати масимальний потік від u до v з прийнятою за 1 ємністю всіх ребер в G в обидва напрямки. Граф є k-реберно-зв'язним тоді і тільки тоді, коли максимальний потік від u до v дорівнює щонаймеше k для будь-якої пари (u,v), тобто k це найменший u-v-потік між усіма (u,v).

Якщо V це кількість вершин в графі, цей простий алгоритм виконає O(V^2) ітерацій iterations задачі про максимальний потік, які можуть бути розв'язаними за O(V^3) час. Отже, складність цього алгоритму загалом складає O(V^5).

Пов'язана задача: знаходження найменшого kреберно-зв'язного підграфа графа G (тобто: виділити настільки мало наскільки можливо ребер в G так, що виділення залишається k-реберно-зв'язним) є NP-складною для k\geq 2.[1]

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.