117
правок
Изменения
→Нахождение вершинной связности
== Нахождение вершинной связности ==
Нахождение вершинной связности сводится к задаче нахождения реберной связности следующим образом.
Разобьем каждую вершину <tex>v</tex> графа на две вершины <tex>v_1</tex> и <tex>v_2</tex>. Все ребра, которые входили в <tex>v</tex> будут входить в <tex>v_1</tex>. Все ребра, которые выходили из <tex>v</tex> будут выходить из <tex>v_2</tex>. Так же добавим ребро <tex>(v_1, v_2)</tex>.
[[Файл:Menger-vertex.JPG|300px|left|thumb|Иллюстрация]]
В новом графе запустим алгоритм нахождения реберной связности.
== Литература ==
