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