Kružnica (teória grafov): Rozdiel medzi revíziami

'''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ý graf|orientovaná]] i neorientovaná.

 

* orientovaný graf

:<math>e_i = \left( v_i, v_{i+1} \right), i = 1, \ldots, n - 1</math> a <math>e_n = \left( v_n, v_1 \right)</math>

 

* neorientovaný graf

:<math>e_i = \left \{ v_i, v_{i+1} \right \}, i = 1, \ldots, n - 1</math> a <math>e_n = \left \{ v_n, v_1 \right \}</math>

 

== Vlastnosti kružnice ==

* [[hamiltonovská kružnica]] - opíše všetky vrcholy grafu, nevstupuje do vrcholu viackrát, hrany nemusí obsahovať všetky

* [[bipartitný|kružnica v bipartitnom grafe]] (vrcholy sú rozdelené do dvoch častí, hrany vedú iba medzi časťami navzájom)

 

{{Preklad|cs|Kružnice (graf)}}