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

orientovaný graf

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

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

neorientovaný graf

${\displaystyle e_{i}=\left\{v_{i},v_{i+1}\right\},i=1,\ldots ,n-1}$ a ${\displaystyle 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