Co dalej policzyć?
Jeśli analizujesz graf, przydadzą się też kalkulatory dotyczące jego stopni, drzew, grafu pełnego i macierzy sąsiedztwa.
Do czego służy kalkulator ścieżek i cykli w grafie?
W kalkulatorze ścieżek i cykli w grafie sprawdzisz, czy podany ciąg wierzchołków jest poprawnym przejściem po krawędziach grafu. Narzędzie rozróżnia drogę, szlak, ścieżkę, cykl oraz przejście zamknięte.
W grafie skierowanym znaczenie ma również kierunek łuku. Dlatego A→B i B→A są dwoma różnymi łukami, a ciąg A,B,A może być cyklem skierowanym długości 2, jeśli oba łuki istnieją.
Jak sprawdzany jest ciąg?
Kalkulator dzieli ciąg na kolejne pary. Dla A,B,C,D sprawdza A-B, B-C i C-D. Jeśli każda potrzebna krawędź istnieje, przejście jest poprawne. Potem sprawdzane są powtórzenia krawędzi i wierzchołków.
Droga / przejście
Każda kolejna para wierzchołków jest połączona odpowiednią krawędzią lub łukiem.
Szlak
Przejście jest poprawne i żadna krawędź nie jest użyta drugi raz.
Ścieżka prosta
Przejście jest poprawne i żaden wierzchołek się nie powtarza.
Cykl
Początek i koniec są takie same, a wewnętrzne wierzchołki i użyte krawędzie się nie powtarzają.
Przykład
Załóżmy, że graf nieskierowany ma krawędzie A-B, B-C, C-D, D-A, B-D, C-E, a sprawdzany ciąg to A,B,C,D,A. Kalkulator sprawdza pary A-B, B-C, C-D i D-A.
Wszystkie krawędzie istnieją. Pierwszy i ostatni wierzchołek są takie same, a w środku nie ma powtórzeń, więc jest to cykl długości 4.
Zadania
Spróbuj najpierw odpowiedzieć samodzielnie, a potem pokaż odpowiedzi.
Graf: A-B, B-C, C-D, D-A. Czy A,B,C,D,A jest cyklem?
Graf: A-B, B-C, C-D. Czy A,B,C,D jest ścieżką?
Graf: A-B, B-C. Czy A,C jest poprawnym przejściem?
Graf: A-B, B-C, C-A. Czy A,B,C,A jest cyklem?
Odpowiedź 1: Tak, to cykl długości 4.
Odpowiedź 2: Tak, to ścieżka prosta długości 3.
Odpowiedź 3: Nie, bo brakuje krawędzi A-C.
Odpowiedź 4: Tak, to cykl długości 3.
Droga, szlak, ścieżka i cykl
Droga / przejście
Wierzchołki: mogą się powtarzać.
Krawędzie: mogą się powtarzać.
Zamknięte: może być.
Szlak
Wierzchołki: mogą się powtarzać.
Krawędzie: nie mogą się powtarzać.
Zamknięte: może być.
Ścieżka prosta
Wierzchołki: nie mogą się powtarzać.
Krawędzie: nie powtarzają się.
Zamknięte: nie.
Cykl
Wierzchołki: pierwszy = ostatni, wewnątrz bez powtórzeń.
Krawędzie: bez powtórzeń.
Zamknięte: tak.
Najczęstsze błędy
- Mylenie ścieżki z drogą – ścieżka prosta nie powtarza wierzchołków.
- Brak ostatniej krawędzi w cyklu – zamknięcie ciągu musi także istnieć w grafie.
- Ignorowanie kierunku – w grafie skierowanym A→B nie oznacza B→A.
- Powtórzona krawędź w szlaku – szlak nie może używać tej samej krawędzi drugi raz.
Ciekawostka
Problem znajdowania ścieżek w grafie jest podstawą nawigacji, wyszukiwania tras, sieci komputerowych i analizy połączeń. Podobne pojęcia pojawiają się w algorytmach BFS, DFS i Dijkstry.
Cały pakiet: matematyka dyskretna, logika, zbiory i grafy
Jeżeli pracujesz z logiką i zbiorami, przejdź przez tablicę prawdy, prawa De Morgana, działania na zbiorach oraz relacje i własności relacji.
Do zadań z resztami z dzielenia przydadzą się modulo, kongruencje liniowe i rozszerzony algorytm Euklidesa.
Wskazówka
Gdy sprawdzasz cykl, najpierw wypisz wszystkie pary kolejnych wierzchołków i sprawdź, czy każda para ma krawędź. Dopiero potem oceniaj powtórzenia wierzchołków i krawędzi.
Cały dział matematyki dyskretnej: Akademia matematyki dyskretnej – logika, zbiory i grafy.
Aktualizacja: 29.09.2026