Zobrazenie zdroja stránky Kružnica (teória grafov)

[[Súbor:Orientovaná kružnice.svg|thumb|right|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ý graf|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 (teória grafov)|strom]]).

== Definícia ==
Kružnica je graf <math>C_n = (V, E)</math>, kde <math>V = \left \{ v_1, \ldots, v_n \right \}</math> a <math>E = \left \{ e_1, \ldots, e_n \right \}</math> a platí:
* 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>
:: každý vrchol orientovanej kružnice má vstupný i výstupný stupeň rovný 1

* 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>
:: každý vrchol neorientovanej kružnice má [[stupeň vrcholu|stupeň]] 2.<ref>{{Citácia elektronického dokumentu
 | priezvisko = Znám
 | meno = Štefan
 | odkaz na autora = 
 | vydavateľ = Matematicko-fyzikálna fakulta Univerzity Komenského
 | titul = Kombinatorika a teória grafov
 | url = 
 | dátum vydania = 1982
 | dátum prístupu = 1982
 | miesto = Bratislava
 | jazyk = slovenský
}}</ref>

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

== Referencie ==
{{Referencie}}

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

{{Matematický výhonok}}

[[Kategória:Teória grafov]]