V teorii grafů se tyto dva typy objektů běžně označují jako cykly .
Jeden typ cyklu , běžněji označovaný jako uzavřený traversal , sestává ze sekvence vrcholů začínajících a končících ve stejném vrcholu a každé dva po sobě jdoucí vrcholy v sekvenci sousedí. Jiný typ smyčky, někdy nazývaný jednoduchá smyčka , je uzavřený přechod bez přejíždění hrany nebo návštěvy vrcholu dvakrát, s výjimkou počátečního a koncového vrcholu. Jednoduché smyčky lze popsat množinou hran, na rozdíl od uzavřených traverz, ve kterých množiny hran (s možným opakováním) jednoznačně neurčují pořadí vrcholů. Řízený cyklus v digrafu je posloupnost vrcholů začínajících a končících ve stejném vrcholu a v této posloupnosti pro libovolné dva po sobě jdoucí vrcholy existuje oblouk od dřívějšího k pozdějšímu. Stejný rozdíl mezi jednoduchými smyčkami a traverzály jako výše lze udělat pro orientované grafy [1] .
Cyklus bez tětiv v grafu, nazývaný také díra nebo generovaný cyklus, je cyklus, ve kterém žádné dva vrcholy cyklu nejsou spojeny hranou, pokud tato hrana sama do cyklu nepatří. Antidíra je doplňkem díry. K popisu dokonalých grafů lze použít akordové grafy — podle striktní věty o dokonalém grafu je graf dokonalý tehdy a jen tehdy, když neobsahuje díry a antidíry s lichým počtem vrcholů větším než tři. Akordický graf je speciální typ dokonalého grafu, který nemá díry větší než tři.
Obvod grafu je délka nejmenšího cyklu. Tento cyklus nutně nebude mít akordy. Buňky jsou nejmenší pravidelné grafy s daným vrcholovým stupněm a obvodem.
Periferní cyklus je cyklus v grafu s vlastností, že libovolné dvě hrany, které do cyklu nepatří, mohou být spojeny cestou, jejíž vnitřní body do cyklu nepatří. V grafu, který není vytvořen přidáním jedné hrany do cyklu, musí být obvodový cyklus generovaným cyklem.
Pojem cyklu může také odkazovat na prvky prostoru cyklu grafu. Skládá se ze sad hran, které mají pro každý vrchol sudý stupeň. Množiny tvoří vektorový prostor nad konečným polem dvou prvků. Používat metody algebraické topologie , to může být zobecněno k vektorovým prostorům nebo modulům přes jiné prsteny , takový jako celá čísla, reálná čísla, etc. Podle Veblenova teorému , nějaký prvek prostoru cyklů může být získán tím, že kombinuje jednoduché cykly. Základem cyklu grafu je množina jednoduchých cyklů, které tvoří základ prostoru cyklu [2] [3] .
Neorientovaný graf má cyklus právě tehdy, když hloubkové vyhledávání (DFS) najde hranu, která vede do již navštíveného vrcholu (oblouk dozadu) [4] . Stejně tak všechny zadní hrany, které algoritmus DFS najde, jsou součástí cyklů [5] . U neorientovaných grafů trvá nalezení cyklu v grafu s n vrcholy pouze O ( n ) času , protože nejvýše n − 1 hran může být hranami stromu.
Orientovaný graf má cyklus právě tehdy, když DFS najde zpětný oblouk. Dopředné oblouky a příčné oblouky nemusí nutně znamenat cyklus. Mnoho topologických třídicích algoritmů také detekuje cykly, protože narušují existenci topologického řádu. Pokud je orientovaný graf rozdělen na silně propojené složky , existují cykly pouze ve složkách, ale ne mezi nimi, protože cykly jsou silně propojené [5] .
Aplikace algoritmů pro vyhledávání smyček zahrnují čekací grafy pro hledání uváznutí v systémech s paralelními vlákny [6] .
V článku z roku 1736 o problému sedmi můstků z Königsbergu , obecně považovaném za zrod teorie grafů, Leonhard Euler dokázal, že má-li mít konečný neorientovaný graf uzavřený průchod všemi hranami právě jednou, je nutné a postačující, aby byl spojen. a mají sudý stupeň všech vrcholů. Odpovídající popis existence uzavřeného průchodu každé hrany právě jednou v orientovaném grafu vyžaduje, aby byl graf silně propojený a aby každý vrchol měl stejný počet příchozích a odchozích oblouků. V obou případech je výsledná cesta známá jako Eulerův cyklus . Pokud má konečný neorientovaný graf sudý stupeň každého vrcholu, ať už je souvislý nebo ne, lze najít sadu jednoduchých cyklů, které pokrývají každou hranu právě jednou – to je Veblenova věta [7] . Pokud souvislý graf nesplňuje podmínky Eulerovy věty, lze v polynomiálním čase stále nalézt uzavřený průchod minimální délky pokrývající všechny hrany alespoň jednou řešením problému silniční kontroly..
Úkol najít jednoduchý cyklus, který prochází každým vrcholem přesně jednou, na rozdíl od krytí hran, je mnohem obtížnější. Takové cykly jsou známé jako Hamiltonovské cykly a problém určení, zda takové cykly existují, je NP-úplný [8] . Bylo publikováno mnoho studií o třídách grafů, které zjevně obsahují hamiltonovské cykly. Příkladem je Oreova věta, že hamiltonovský cyklus lze v grafu nalézt vždy, pokud sečtením stupňů libovolné dvojice nesousedících vrcholů získáme alespoň celkový počet vrcholů grafu [9] .
Dohad pokrytí dvojitým cyklem uvádí, že pro jakýkoli bezmůstkový graf existuje více množin jednoduchých cyklů, které pokrývají každou hranu grafu přesně dvakrát. Dosud nebyl nalezen žádný důkaz domněnky nebo protipříkladu [10] .
Některé důležité třídy grafů lze definovat nebo popsat jejich cykly. To: