Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


2. Základní pojmy / Kružnice (cyklus) v grafu

Definice

Kružnicí (cyklem) v grafu rozumíme posloupnost vrcholů a hran (v0, e1, v1,..., et, vt = v0), kde vrcholy v0,..., vt-1 jsou navzájem různé vrcholy grafu G a pro každé i = 1,2,...,t je ei = {vi-1, vi} je prvkem E(G).

Poznámka

Nejkratší kružnicí je trojúhelník (K3 - úplný graf se třemi vrcholy).

Povšimněte si, že definice kružnice se podobá definici cesty - opět jde o posloupnost hran a vrcholů. Na rozdíl od cesty je ale první a poslední vrchol posloupnosti stejný. V cestě ale povolujeme i délku 0 (prázdnou posloupnost). Kružnice má přitom minimální délku 3.

Příklady

Nejkratší kružnice (trojúhelník)
Obr. č. 2.12 - Nejkratší kružnice (trojúhelník)

Kružnice v obecném grafu
Obr. č. 2.13 - Kružnice v obecném grafu

Acyklický graf

Graf nazýváme acyklický, pokud neobsahuje cyklus.


Úvod

Základní pojmy

Vybrané problémy

Procvičování