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ů.

Orientovaná kružnice na pěti vrcholech.

V neorientovaném grafu nemá smysl hovořit o cyklu délky 1; v orientovaném se nazývá smyčka, jde o uzel, v němž některá hrana začíná i končí.

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ů

Acyklické grafy

Graf, který neobsahuje (jako svůj podgraf) cyklus, se nazývá acyklický. Z výše uvedeného vyplývá, že

• Neorientovaný graf $(V,E)$ - tj. takový, kde hrany jsou (neuspořádané) dvouprvkové podmnožiny $V$ - je acyklický, právě když neobsahuje žádnou posloupnost vrcholů $(v_{1},v_{2},\ldots ,v_{n})$ pro nějaké $n\geq 2$ takovou, že pro každé $0<i\leq n$ platí $\{v_{i},v_{i+1}\}\in E$, označíme-li pro snazší zápis uzel $v_{1}$ zároveň výrazem $v_{n+1}$.
• Obdobně orientovaný graf $(V,E)$ - tj. takový, jehož hrany jsou uspořádané dvojice prvků z $V$ - je acyklický, právě když neobsahuje žádnou posloupnost vrcholů $(v_{1},v_{2},\ldots ,v_{n})$, kde $v_{n+1}=v_{1}$, pro $n\geq 1$, takovou, že pro každé $0<i\leq n$ platí $(v_{i},v_{i+1})\in E$.

U orientovaného grafu připouštíme i $n=1$, tj. acyklický není graf obsahující smyčku, tj. hranu končící v bodě, v němž začíná.

Externí odkazy

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

Portály: Matematika