Cykl (teoria grafów)

Przykładowy graf cykliczny

Cykl grafu – zamknięta droga prosta $e_a,e_b,\dots ,e_z,$ taka że krawędź $e_z$ kończy się w początkowym wierzchołku drogi.

Rodzaje cykli

• Cykl prosty to droga zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem). Cykl prosty jest szczególnym (prostszym) przypadkiem cyklu.
• Cykl Hamiltona – cykl prosty przebiegający przez wszystkie wierzchołki grafu i przechodzący przez nie dokładnie 1 raz (oprócz pierwszego wierzchołka).
• 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).

Twierdzenie

Jeżeli najmniejszy stopień wierzchołka w grafie $G$ jest nie mniejszy niż $2,$ to graf $G$ zawiera cykl.

Dowód twierdzenia

Oznaczmy najmniejszy stopień wierzchołka w grafie $G$ przez $\delta .$ Na podstawie lematu o uściskach dłoni wiemy, że:

$2m=\mathrm{deg}(v_1)+\dots +\mathrm{deg}(v_n).$

Ponieważ każdy wierzchołek grafu $G$ (z założenia) jest stopnia co najmniej $2,$ możemy zapisać, że:

$\mathrm{deg}(v_1)+\dots +\mathrm{deg}(v_n)⩾n\delta ⩾2n.$

Po przekształceniu otrzymujemy:

$2m⩾2n⟹m⩾n.$

Jak widać, liczba krawędzi w grafie $(m)$ jest większa lub równa od liczby wierzchołków $(n).$ Łatwo zauważyć, że wobec tego w grafie $G$ występuje przynajmniej jeden cykl, co kończy dowód.

Wyjaśnienie: stworzenie ścieżki (lub drzewa) o $n$ wierzchołkach (niezawierają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.