В теорії графів, граф 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 це кількість вершин в графі, цей простий алгоритм виконає ітерацій iterations задачі про максимальний потік, які можуть бути розв'язаними за час. Отже, складність цього алгоритму загалом складає .
Пов'язана задача: знаходження найменшого kреберно-зв'язного підграфу графу G (тобто: виділити настільки мало наскільки можливо ребер в G так, що виділення залишається k-реберно-зв'язним) є NP-складною для .
Див. також
Примітки
- M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет