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
Maksymalna ilość ścieżek
Maksymalna ilość ścieżek
Ostatnio zmieniony 20 cze 2019, o 23:27 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Używaj LaTeXa także do pojedynczych symboli.
Powód: Używaj LaTeXa także do pojedynczych symboli.
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Maksymalna ilość ścieżek
Ten punkt jest dla mnie mało czytelny bo w przeciwnym przypadku sugerowałbym grafy dwudzielne...każdy wierzchołek może być użyty co maksymalnie jeden raz
-
- Moderator
- Posty: 2828
- Rejestracja: 15 cze 2008, o 15:45
- Płeć: Mężczyzna
- Lokalizacja: Seattle, WA
- Podziękował: 3 razy
- Pomógł: 356 razy
Re: Maksymalna ilość ścieżek
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}\).