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 $C_{n}=(V,E)$, kde $V=\left\{v_{1},\ldots ,v_{n}\right\}$ a $E=\left\{e_{1},\ldots ,e_{n}\right\}$ a platí:

orientovaný graf

$e_{i}=\left(v_{i},v_{i+1}\right),i=1,\ldots ,n-1$ a $e_{n}=\left(v_{n},v_{1}\right)$

každý vrchol orientované kružice má vstupní i výstupní stupeň roven 1

neorientovaný graf

$e_{i}=\left\{v_{i},v_{i+1}\right\},i=1,\ldots ,n-1$ a $e_{n}=\left\{v_{n},v_{1}\right\}$

každý vrchol neorientované kružnice má stupeň 2

Vlastnosti

Kružnice je graf:

• souvislý
• regulární
• eulerovský
• bipartitní, obsahuje-li sudý počet vrcholů

Portály: Matematika