Kružnica (teória grafov)

graf, ktorý sa skladá z jediného cyklu

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á.

Orientovaná kružnica na piatich vrcholoch

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ť

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ť
  • 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ť
  1. ZNÁM, Štefan. Kombinatorika a teória grafov. Bratislava: Matematicko-fyzikálna fakulta Univerzity Komenského, 1982, [cit. 1982-10-04].

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