Kružnice (graf)
Appearance
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f9/Orientovan%C3%A1_kru%C5%BEnice.svg/220px-Orientovan%C3%A1_kru%C5%BEnice.svg.png)
V teorii grafů se termínem kružnice (též cyklus) označuje takový graf, který se skládá z jediného cyklu – tedy uzavřené posloupnosti propojených vrcholů. Kružnice může být orientovaná i neorientovaná.
Graf, který jako podgraf obsahuje kružnici, se nazývá cyklický. V opačném případě se nazývá acyklický (viz strom).
Definice[editovat | editovat zdroj]
Kružnice je graf , kde a a platí:
- orientovaný graf
- a
- každý vrchol orientované kružice má vstupní i výstupní stupeň roven 1
- neorientovaný graf
- a
- každý vrchol neorientované kružnice má stupeň 2
Vlastnosti[editovat | editovat zdroj]
Kružnice je graf:
- souvislý
- regulární
- eulerovský
- bipartitní, obsahuje-li sudý počet vrcholů
Externí odkazy[editovat | editovat zdroj]
Obrázky, zvuky či videa k tématu kružnice na Wikimedia Commons