Cykl (teoria grafów)

Zobacz też: inne znaczenia słowa „cykl”.

Cykl grafu – zamknięta droga prosta ${\displaystyle e_{a},e_{b},\dots ,e_{z},}$ taka że krawędź ${\displaystyle e_{z}}$ kończy się w początkowym wierzchołku drogi^[1].

• Cykl prosty to droga zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem)^[2]. 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).

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

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

${\displaystyle 2m=\deg(v_{1})+\ldots +\deg(v_{n}).}$

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

${\displaystyle \deg(v_{1})+\ldots +\deg(v_{n})\geqslant n\delta \geqslant 2n.}$

Po przekształceniu otrzymujemy:

${\displaystyle 2m\geqslant 2n\Longrightarrow m\geqslant n.}$

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

Wyjaśnienie: stworzenie ścieżki (lub drzewa) o ${\displaystyle n}$ wierzchołkach (niezawierającej cykli) pozwala „zużyć” do połączenia co najwyżej ${\displaystyle n-1}$ krawędzi. Ostatnia, ${\displaystyle n}$-ta krawędź, jaką musimy „dołożyć” do grafu zgodnie z założeniami, utworzy cykl.