Cykl (teoria grafów)

termin teorii grafów

Cykl grafu – zamknięta droga prosta taka że krawędź kończy się w początkowym wierzchołku drogi[1].

Przykładowy graf cykliczny

Rodzaje cykli edytuj

  • 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).

Twierdzenie edytuj

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

Dowód twierdzenia edytuj

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

 

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

 

Po przekształceniu otrzymujemy:

 

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

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

Przypisy edytuj

  1. Kenneth A. Ross, Charles R.B. Wright: Matematyka dyskretna. Warszawa: 2005, s. 146. ISBN 83-0114-380-0.
  2. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 7. ISBN 0-387-95014-1.