Kružnice (graf)

Z Multimediaexpo.cz

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 = {v_{1}, \dots, v_{n}}$ a $E = {e_{1}, \dots, e_{n}}$ a platí:

orientovaný graf: $e_{i} = (v_{i}, v_{i + 1}), i = 1, \dots, n - 1$ a $e_{n} = (v_{n}, v_{1})$; každý vrchol orientované kružice má vstupní i výstupní stupeň roven 1
neorientovaný graf: $e_{i} = {v_{i}, v_{i + 1}}, i = 1, \dots, n - 1$ a $e_{n} = {v_{n}, v_{1}}$; 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ů

[zobrazit] Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii