Co to jest wykres, który można przemierzać w teorii grafów?

W kontekście teorii grafów graf, po którym można przechodzić, to graf, na którym można przejść przez wszystkie wierzchołki i krawędzie. Innymi słowy, jest to graf, który pozwala nam odwiedzić każdy wierzchołek dokładnie raz i powrócić do wierzchołka początkowego.

Graf, po którym można się poruszać, nazywany jest również grafem spójnym, ponieważ jest to graf, w którym wszystkie wierzchołki są ze sobą połączone .

Rozważmy na przykład prosty graf z trzema wierzchołkami A, B i C, gdzie istnieje krawędź między A i B, krawędź między B i C oraz krawędź między A i C. Ten graf można przemierzać, ponieważ możemy zacznij od wierzchołka A, podążaj krawędziami do B, potem do C i wróć do A.

Z drugiej strony graf z dwoma rozłączonymi składowymi, np. dwa oddzielne grafy, nie jest przejezdny, ponieważ nie jest możliwe odwiedzenie każdego wierzchołka dokładnie raz i powróć do wierzchołka początkowego.