Maksymalna ilość ścieżek

[Yki123]

Hej, dostałem jako pracę zaliczeniową na jednej z Warszawskich uczelni kilka zadań do rozwiązania. Z jednym mam duży problem gdyż nie wiem jak do tego podejść. Czy ktoś ma jakiś pomysł i podsunie rozwiązanie. Będę bardzo wdzięczny!

Mamy sobie graf \(\displaystyle{ F}\). Dla danego grafu \(\displaystyle{ F}\) i wierzcholkow \(\displaystyle{ Q}\) i \(\displaystyle{ W}\) ( wierzchołki \(\displaystyle{ Q}\) i \(\displaystyle{ W}\) należą do grafu \(\displaystyle{ F}\)) potrzeba znaleźć ile jest ścieżek z \(\displaystyle{ Q}\) do \(\displaystyle{ W}\)takich ze każdy wierzchołek może być uzyty co maksymalnie jeden raz.
Problem znalezienia maksymalnej ilości ścieżek należy sprowadzić do problemu maksymalnego przepływu. Jakies pomysły ??



Pozdrawiam

[arek1357]

każdy wierzchołek może być użyty co maksymalnie jeden raz

Ten punkt jest dla mnie mało czytelny bo w przeciwnym przypadku sugerowałbym grafy dwudzielne...

[Afish]

Każdy wierzchołek \(\displaystyle{ X}\) poza \(\displaystyle{ Q}\) i \(\displaystyle{ W}\) zamień na parę wierzchołków \(\displaystyle{ X_i}\) i \(\displaystyle{ X_o}\), następnie zrób krawędź z \(\displaystyle{ X_i}\) do \(\displaystyle{ X_o}\) o pojemności \(\displaystyle{ 1}\). Wszystkie pozostałe krawędzie grafu niech mają dowolnie wielką pojemność, a następnie znajdź maksymalny przepływ z \(\displaystyle{ Q}\) do \(\displaystyle{ W}\).