Kružnica (teória grafov)

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 , kde a a platí:

  • orientovaný graf
a
každý vrchol orientovanej kružnice má vstupný i výstupný stupeň rovný 1
  • neorientovaný graf
a
každý vrchol neorientovanej kružnice má stupeň 2.[1]

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)

Referencie[upraviť | upraviť zdroj]

  1. ZNÁM, Štefan. Kombinatorika a teória grafov [online]. Bratislava : Matematicko-fyzikálna fakulta Univerzity Komenského, 1982, [cit. 1982-11-09].

Zdroj[upraviť | upraviť zdroj]

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