V sobotu 2. listopadu proběhla mohutná oslava naší plnoletosti !!
Multimediaexpo.cz je již 18 let na českém internetu !!
V tiskové zprávě k 18. narozeninám brzy najdete nové a zásadní informace.

Kružnice (graf)

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)
m (1 revizi)
(+ Nový článek)
Řádka 1: Řádka 1:
-
{{Wikipedia-cs|Kružnice (graf)|700}}
+
[[Soubor:Orientovaná kružnice.png|thumb|230px|Orientovaná kružnice na pěti vrcholech.]]
 +
V [[teorie grafů|teorii grafů]] se termínem '''kružnice''' (též '''cyklus''') označuje takový [[Graf (teorie grafů)|graf]], který se skládá z jediného ''cyklu'' - tedy uzavřené [[posloupnost]]i propojených vrcholů. Kružnice může být [[orientovaný graf|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 (graf)|strom]]).
 +
 +
== Definice ==
 +
Kružnice je graf <math>C_n = (V, E)</math>, kde <math>V = \left \{ v_1, \ldots, v_n \right \}</math> a <math>E = \left \{ e_1, \ldots, e_n \right \}</math> a platí:
 +
; orientovaný graf
 +
: <math>e_i = \left( v_i, v_{i+1} \right), i = 1, \ldots, n - 1</math> a <math>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
 +
: <math>e_i = \left \{ v_i, v_{i+1} \right \}, i = 1, \ldots, n - 1</math> a <math>e_n = \left \{ v_n, v_1 \right \}</math>
 +
: každý vrchol neorientované kružnice má [[stupeň vrcholu|stupeň]] 2
 +
 +
== Vlastnosti ==
 +
Kružnice je graf:
 +
* [[souvislý graf|souvislý]]
 +
* [[regulární graf|regulární]]
 +
* [[eulerovský graf|eulerovský]]
 +
* [[bipartitní graf|bipartitní]], obsahuje-li sudý počet vrcholů
 +
 +
 +
{{Článek z Wikipedie}}
 +
[[Kategorie:Typy grafů]]
[[Kategorie:Grafové pojmy]]
[[Kategorie:Grafové pojmy]]

Verze z 8. 10. 2015, 09:40

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 <math>C_n = (V, E)</math>, kde <math>V = \left \{ v_1, \ldots, v_n \right \}</math> a <math>E = \left \{ e_1, \ldots, e_n \right \}</math> a platí:

orientovaný graf
<math>e_i = \left( v_i, v_{i+1} \right), i = 1, \ldots, n - 1</math> a <math>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
<math>e_i = \left \{ v_i, v_{i+1} \right \}, i = 1, \ldots, n - 1</math> a <math>e_n = \left \{ v_n, v_1 \right \}</math>
každý vrchol neorientované kružnice má stupeň 2

Vlastnosti

Kružnice je graf: