Kružnice (graf)

Orientovaná kružnice na pěti vrcholech.

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

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

Kružnice je graf:

Externí odkazy

Média použitá na této stránce

Orientovaná kružnice.svg
Autor: , Licence: CC BY-SA 3.0
Orientovaná kružnice