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

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

Формальне визначення

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

Властивості

• Мінімальний степінь вершин k-реберно-зв'язного графу не менший від k.
• Критичний граф із хроматичним числом >k є 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 це кількість вершин в графі, цей простий алгоритм виконає ${\displaystyle O(V^{2})}$ ітерацій iterations задачі про максимальний потік, які можуть бути розв'язаними за ${\displaystyle O(V^{3})}$ час. Отже, складність цього алгоритму загалом складає ${\displaystyle O(V^{5})}$.

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

Див. також

• K-вершинно-зв'язний граф
• Теорема Менґера
• Зв'язний граф

Примітки

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