Kružnica (teória grafov)

Orientovaná kružnica na piatich vrcholoch

Kružnica alebo cyklus alebo uzavrený ťah v teórii grafov označuje taký graf, ktorý sa skladá z jediného cyklu – teda uzavretej postupnosti prepojených vrcholov. Kružnica môže byť orientovaná i neorientovaná.

Graf, ktorý ako podgraf obsahuje kružnicu, sa nazýva cyklický. V opačnom prípade sa nazýva acyklický (pozri strom).

Definícia

Kružnica je graf $C_n=(V,E)$, kde $V=\{v_1,\dots ,v_n\}$ a $E=\{e_1,\dots ,e_n\}$ a platí:

• orientovaný graf

$e_i=(v_i,v_{i+1}),i=1,\dots ,n-1$ a $e_n=(v_n,v_1)$

každý vrchol orientovanej kružnice má vstupný i výstupný stupeň rovný 1

• neorientovaný graf

$e_i=\{v_i,v_{i+1}\},i=1,\dots ,n-1$ a $e_n=\{v_n,v_1\}$

každý vrchol neorientovanej kružnice má stupeň 2.

Vlastnosti kružnice

• eulerovská kružnica – opíše všetky hrany grafu, viackrát tú istú hranu nepoužíva, do vrcholu môže vstupovať viackrát
• hamiltonovská kružnica – opíše všetky vrcholy grafu, nevstupuje do vrcholu viackrát, hrany nemusí obsahovať všetky
• kružnica v bipartitnom grafe (vrcholy sú rozdelené do dvoch častí, hrany vedú iba medzi časťami navzájom)