Droga (teoria grafów)

Droga – ścieżka, w której wierzchołki są różne (z wyjątkiem ewentualnej równości wierzchołków pierwszego i ostatniego – mamy wtedy do czynienia ze szczególnym rodzajem drogi, drogą zamkniętą, tzw. cyklem).

Właściwości

Wprost z definicji, wynikają proste własności drogi.

Podgraf utworzony tylko z wierzchołków i krawędzi łączących kolejne wierzchołki drogi, ma wierzchołek rzędu 2, poza pierwszym i ostatnim w przypadku ich braku cyklu (wtedy mają one oba rząd 1). Tym samym podgraf ten (droga) jest acykliczny.

W przypadku drogi o długości 3 (zawierającej 3 różne wierzchołki,) lub większej, oznacza to również, że każda krawędź (można zignorować skierowanie krawędzi) przechodzona jest dokładnie raz. W przypadku drogi o długości 2, mamy do czynienia z jedną krawędzią i jest ona przechodzona raz lub dwa (jeśli droga jest cykliczna). W przypadku drogi o długości 1, nie mamy krawędzi.

Zobacz też

• ścieżka (teoria grafów)
• cykl (teoria grafów)