Loading AI tools
З Вікіпедії, вільної енциклопедії
В теорії графів, граф 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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.