Kružnica (graf)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
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ýva acyklický (pozri strom).

Definícia[upraviť | upraviť zdroj]

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žnice 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

Vlastnosti kružnice[upraviť | upraviť zdroj]

  • eulerovská kružnica – opíše všetky hrany grafu, viackrát tú istú hranu nepoužíva, do vrcholu môže vstupovať viackrát
  • hamiltonovská kružnica – opíše všetky vrcholy grafu, nevstupuje do vrcholu viackrát, hrany nemusí obsahovať všetky
  • kružnica v bipartitnom grafe (vrcholy sú rozdelené do dvoch častí, hrany vedú iba medzi časťami navzájom)

Tento článok je čiastočný alebo úplný preklad článku Kružnice (graf) na českej Wikipédii (číslo revízie nebolo určené).