Droga (teoria grafów)
Z Wikipedii
Zajrzyj na stronę dyskusji, by dowiedzieć się odnośnie jakich informacji pojawiły się wątpliwości.
Wstawiając szablon dodaj informację o tej stronie na Wikipedia:Strony wymagające weryfikacji.
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Droga – w teorii grafów termin oznaczający łańcuch (marszruta o różnych gałęziach) pozwalającą na przemieszczanie się po krawędziach grafów między ich wierzchołkami. Jeżeli graf jest nieskierowany, to możliwy jest ruch po drodze w obie strony. Jeżeli graf jest skierowany, to poruszanie się po niej jest możliwe tylko jednym kierunku. Ruch "pod prąd" jest zabroniony. W takiej sytuacji droga w grafie jest łańcuchem skierowanym (marszrutą skierowaną).
[edytuj] Definicja matematyczna
Łańcuch Ł jest drogą w pewnym grafie:
- G=<W,U,P>
wtedy i tylko wtedy, gdy poniższa implikacja jest prawdziwa:
- Jeżeli x,u,y są dowolnymi trzema kolejnymi elementami tego łańcucha, przy czym:
- i
- to u na pewno nie jest łukiem "wychodzącym" od y:
W grafach zwykłych wszystkie łańcuchy są drogami.
