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-06-03].
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é).
🔥 Top keywords: Hlavná stránkaŠpeciálne:HľadanieMajstrovstvá sveta vo futbale 2026Alex PereiraWikipédia:Wiki miluje ZemMajstrovstvá Európy vo futbale 2024Špeciálne:PoslednéÚpravyCristiano RonaldoMajstrovstvá Európy vo futbaleRozhlas a televízia SlovenskaSlovenskoKvalifikácia na Majstrovstvá sveta vo futbale 2026 – Severná AmerikaLadislav BorbélyMarine Le PenováMajstrovstvá sveta vo futbaleSlovinskoSupercelaČlenovia Európskej únieYouTubeCéline DionováZoznam smerových telefónnych čísiel štátovFrancesco CalzonaIvan SchranzMajstrovstvá Európy vo futbale 2020Kylian MbappéPepeSlovenské národné futbalové mužstvoZoznam okresov na SlovenskuCyril a MetodLionel MessiBelgickoPeter Sagan1. júlBratislavaAlžbeta FerencováStudienkaTomáš ValášekSlovenská televízia a rozhlasPravica (politika)