Мне нужно объяснение о том, какие именно узловые непересекающиеся пути? и Как определить максимальное количество непересекающихся узлов между двумя узлами Source (s) и Sink (t) в ориентированном графе. Может ли кто-нибудь объяснить графически.Что такое узловые непересекающиеся пути?
Путь - это последовательность вершин: s, v_1, .., v_m, t. Два пути s, v_1, .., v_m, t и s, u_1, ..., u_k, t называются узлами-непересекающимися, если v_i != u_j для любых действительных i и j.
Мы можем уменьшить эту проблему до нахождения максимального числа путей, не связанных друг с другом, путем разбиения каждой вершины (кроме источника и цели) на две части, добавление ребра из первой копии во вторую копию, перенаправление всех ребер это конец этой вершины для первой копии и всех исходящих ребер из второй копии. После этого ответ будет максимальным потоком в этом графике (все ребра должны иметь единицу мощности).
здесь я не понял, что именно означает разделение каждой вершины на две части. –
@praveenkumarbeedanal Это означает создание нового графика, где есть пара вершин вместо каждой вершины (кроме источника и цели), а ребра добавляются, как описано в моем ответе. – kraskevich
ладно спасибо. –
Это может помочь: https://www.quora.com/How-can-I-approach-the-problem-Intergalactic-Map-IM-on-SPOJ-using-Max-Flow/answer/Raziman-TV –