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

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=\{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ů

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,\dots ,v_n)$ pro nějaké $n\ge 2$ takovou, že pro každé $0<i\le 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,\dots ,v_n)$, kde $v_{n+1}=v_1$, pro $n\ge 1$, takovou, že pro každé $0<i\le 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

• Šablona:Commonscat