Loading AI tools
Z Wikipedii, wolnej encyklopedii
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).
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.