Kružnice (graf)

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,\dots <!--\; \dots \; -->,v_n\right\}$ a $E=\left\{e_1,\dots <!--\; \dots \; -->,e_n\right\}$ a platí:

orientovaný graf

$e_i=\left(v_i,v_{i+1}\right),i=1,\dots <!--\; \dots \; -->,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,\dots <!--\; \dots \; -->,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ů

Externí odkazy

• Obrázky, zvuky či videa k tématu kružnice na Wikimedia Commons

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.