V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!
Multimediaexpo.cz je již 18 let na českém internetu !!
Kružnice (graf)
Z Multimediaexpo.cz
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)</math>, kde \(V = \left \{ v_1, \ldots, v_n \right \}</math> a \(E = \left \{ e_1, \ldots, e_n \right \}</math> a platí:
- orientovaný graf
- \(e_i = \left( v_i, v_{i+1} \right), i = 1, \ldots, n - 1</math> a \(e_n = \left( v_n, v_1 \right)</math>
- 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</math> a \(e_n = \left \{ v_n, v_1 \right \}</math>
- 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ů
| 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. |