náhled|vpravo|Orientovaná kružnice na pěti vrcholech. V teorii grafů se termínem kružnice (též cyklus) označuje takový graf, který se skládá z jediného cyklu – tedy uzavřené posloupnosti propojených vrcholů.
V neorientovaném grafu nemá smysl hovořit o cyklu délky 1; v orientovaném se nazývá smyčka, jde o uzel, v němž některá hrana začíná i končí.
Graf, který jako podgraf obsahuje kružnici, se nazývá cyklický. V opačném případě se nazývá acyklický (viz strom).
Definice Kružnice je graf , kde a a platí: orientovaný graf a každý vrchol orientované kružice má vstupní i výstupní stupeň roven 1 neorientovaný graf a každý vrchol neorientované kružnice má stupeň 2
Vlastnosti Kružnice je graf: souvislý regulární eulerovský bipartitní, obsahuje-li sudý počet vrcholů
Acyklické grafy
Graf, který neobsahuje (jako svůj podgraf) cyklus, se nazývá acyklický. Z výše uvedeného vyplývá, že Neorientovaný graf – tj. takový, kde hrany jsou (neuspořádané) dvouprvkové podmnožiny – je acyklický, právě když neobsahuje žádnou posloupnost vrcholů pro nějaké takovou, že pro každé platí , označíme-li pro snazší zápis uzel zároveň výrazem . Obdobně orientovaný graf – tj. takový, jehož hrany jsou uspořádané dvojice prvků z – je acyklický, právě když neobsahuje žádnou posloupnost vrcholů , kde , pro , takovou, že pro každé platí .
U orientovaného grafu připouštíme i , tj. acyklický není graf obsahující smyčku, tj. hranu končící v bodě, v němž začíná.
Externí odkazy
Kategorie:Rovinné grafy Kategorie:Grafové pojmy