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 це кількість вершин в графі, цей простий алгоритм виконає   ітерацій iterations задачі про максимальний потік, які можуть бути розв'язаними за   час. Отже, складність цього алгоритму загалом складає  .

Пов'язана задача: знаходження найменшого kреберно-зв'язного підграфу графу G (тобто: виділити настільки мало наскільки можливо ребер в G так, що виділення залишається k-реберно-зв'язним) є NP-складною для  .[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.