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> с пропускной способностью <tex>1</tex>.
[[Файл:Vertex-2vertex.png|300px|left|thumb|Иллюстрация]]
