Witam,
Próbuję napisać algorytm znajdujący ścieżkę P5 w grafie. Słyszałem, że można to zrobić podnosząc macierz sąsiedztwa grafu dwa razy do kwadratu, tj.
M - macierz sąsiedztwa
M = M*M
M = M*M
Taka operacja daje nam ilość marszrut długości 4 w danym grafie. Nie mogę znaleźć zależności pomiędzy ilością marszrut, a istnieniem ścieżki. Czy ktoś może spotkał się z takim algorytmem?
Ścieżka P5 w grafie
-
adek05
- Użytkownik
- Posty: 450
- Rejestracja: 3 kwie 2007, o 18:38
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska
- Podziękował: 12 razy
- Pomógł: 68 razy
Ścieżka P5 w grafie
Jeżeli liczba marszrut jest niezerowa, to znaczy, że istnieje taka marszruta, czy tam ścieżka, whatever.
\(\displaystyle{ M^i}\) daje na \(\displaystyle{ a_{k,l}}\) ilość ścieżek długości \(\displaystyle{ i}\).
\(\displaystyle{ M^i}\) daje na \(\displaystyle{ a_{k,l}}\) ilość ścieżek długości \(\displaystyle{ i}\).