Изменения

Перейти к: навигация, поиск

Вершинная, рёберная связность, связь между ними и минимальной степенью вершины

1013 байт убрано, 03:12, 21 октября 2018
→‎Нахождение реберной связности
== Нахождение реберной связности ==
В статье про [[k-связность]] было сформулировано следующее утверждение:
{{Утверждение
|statement=
Граф  <tex> G </tex> является '''реберно <tex> l</tex>-связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
}}
Там же было дано определение реберной связности через <tex> l</tex>-связность:
{{Определение
|definition=
[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l</tex>-связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>.
}}
Для нахождения реберной связности нужно перебрать все пары вершин <tex>s</tex> и <tex>t</tex>, найти количество непересекающихся путей из <tex>s</tex> в <tex>t</tex> и выбрать минимум.
Пусть он равен <tex>l</tex>. По утверждению, граф является [[k-связность#def_2|<tex>l</tex>-связным]], причем такое <tex>l</tex> - максимально (ведь мы явно нашли количество путей). А значит, по определению, реберная связность равна <tex>l</tex>.
Для нахождения количества непересекающихся путей из <tex>s</tex> в <tex>t</tex> воспользуемся алгоритмом нахождения максимального потока. Сопоставим каждому ребру пропускную способность, равную <tex>1</tex> и найдем максимальный [[Определение сети, потока #Определение потока |поток]].
Vsklamm
200
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/66566»

Навигация