Cykl (teoria grafów)


Cykl (teoria grafów) w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Spis treści

Rodzaje cykli | edytuj kod

Cykl prosty to droga zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem)[1].

Cykl (niekoniecznie prosty) to ścieżka zamknięta, z takim samym ostatnim i pierwszym wierzchołkiem. (Dodatkowo ścieżka ta może posiadać wielokrotnie ten sam wierzchołek, również z rzędu – w przypadku tzw. pętli). 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 kod

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

Dowód twierdzenia | edytuj kod

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

2 m = deg ( v 1 ) + + deg ( v n ) . {\displaystyle 2m=\deg(v_{1})+\dots +\deg(v_{n}).}

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

deg ( v 1 ) + + deg ( v n ) n δ 2 n . {\displaystyle \deg(v_{1})+\dots +\deg(v_{n})\geqslant n\delta \geqslant 2n.}

Po przekształceniu otrzymujemy:

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

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

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

Przypisy | edytuj kod

  1. Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 7. ISBN 0-387-95014-1.
Na podstawie artykułu: "Cykl (teoria grafów)" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy