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á.
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
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ť- ↑ ZNÁM, Štefan. Kombinatorika a teória grafov. Bratislava: Matematicko-fyzikálna fakulta Univerzity Komenského, 1982, [cit. 1982-10-04].
Zdroj
upraviťTento článok je čiastočný alebo úplný preklad článku Kružnice (graf) na českej Wikipédii (číslo revízie nebolo určené).