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}$.[1]

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