Kružnica (teória grafov)

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 , kde  a  a platí:
 orientovaný graf
 a 
 každý vrchol orientovanej kružnice má vstupný i výstupný stupeň rovný 1

 neorientovaný graf
 a 
 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)

 Referencie 

 Zdroj 

Kategória:Teória grafov