Cykl (teoria grafów)
Z Wikipedii
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 |
[edytuj] Rodzaje cykli
Cykl to droga (inaczej: ścieżka prosta) zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem).
Cykl prosty – cykl, w którym żaden wierzchołek się nie powtarza:
Cykl Hamiltona – cykl prosty przebiegający przez wszystkie wierzchołki grafu.
Cykl Eulera – cykl zawierający wszystkie krawędzie grafu i przechodzący przez nie dokładnie 1 raz.
Cykl własny – w multigrafie cykl złożony z jednej krawędzi, która zaczyna się i kończy w tym samym wierzchołku (zwany też pętlą własną wierzchołka).
[edytuj] Twierdzenie
- Jeżeli najmniejszy stopień wierzchołka w grafie G jest nie mniejszy niż 2, to graf G zawiera cykl.
[edytuj] Dowód twierdzenia
Oznaczmy najmniejszy stopień wierzchołka w grafie G przez δ. Na podstawie lematu o uściskach dłoni wiemy, że:
.
Ponieważ każdy wierzchołek grafu G (z założenia) jest stopnia co najmniej 2, możemy zapisać, że:
.
Po przekształceniu otrzymujemy:
.
Jak widać, liczba krawędzi w grafie (m) jest większa lub równa od liczby wierzchołków (n). Łatwo widać, że wobec tego w grafie G występuje przynajmniej jeden cykl, co kończy dowód.
Wyjaśnienie: stworzenie ścieżki o n wierzchołkach (nie zawierającej cykli) pozwala "zużyć" do połączenia co najwyżej n − 1 krawędzi. Ostatnia, n-ta krawędź, jaką musimy "dołożyć" do grafu zgodnie z założeniami, utworzy cykl.
