Kružnica (graf)

z Wikipédie, slobodnej encyklopédie

Orientovaná kružnica na piatich vrcholoch.

Kružnica alebo cyklus alebo uzavrený ťah v teórii grafov označuje taký graf, ktorý sa skladá z jediného cyklu - teda uzavretej postupnosti prepojených vrcholov. Kružnica môže byť orientovaná i neorientovaná.

Graf, ktorý ako podgraf obsahuje kružnicu, sa nazýva cyklický. V opačnom prípade sa nazývá acyklický (pozri strom).

[upraviť] Definícia

Kružnica 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 orientovanej kružice má vstupný i výstupný stupeň rovný 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 neorientovanej kružnice má stupeň 2

[upraviť] Vlastnosti

Kružnica je graf:

súvislý
regulárny
eulerovský
bipartitný, ak obsahuje párny počet vrcholov
chromatické číslo kružnice, ak je počet vrcholov párný 2, ak je počet vrcholov nepárny 3

Tento článok je sčasti alebo úplne založený na preklade článku Kružnice (graf) zverejneného na českej Wikipédii.

Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.

Kružnica (graf)

z Wikipédie, slobodnej encyklopédie

[upraviť] Definícia

[upraviť] Vlastnosti

Zobrazení

Osobné nástroje

Navigácia

Hľadať

Nástroje

V iných jazykoch