I grafteorin kallas de två typerna av objekt vanligtvis som cykler .
En typ av cykel , mer allmänt kallad sluten traversal , består av en sekvens av hörn som börjar och slutar vid samma vertex, och varannan på varandra följande hörn i sekvensen är intilliggande. En annan typ av slinga, som ibland kallas en enkel slinga , är sluten traversering utan att dra tillbaka en kant eller besöka en vertex två gånger, förutom start- och slutpunkten. Enkla slingor kan beskrivas med en uppsättning kanter, i motsats till slutna traverser, där uppsättningar av kanter (med möjlig upprepning) inte unikt bestämmer ordningen på hörn. En riktad cykel i en digraf är en sekvens av hörn som börjar och slutar vid samma vertex, och i denna sekvens, för två på varandra följande hörn, finns det en båge från tidigare till senare. Samma distinktion mellan enkla loopar och traverseringar som ovan kan göras för riktade grafer [1] .
En cykel utan ackord i en graf, även kallad ett hål eller en genererad cykel, är en cykel där inga två hörn av cykeln är förbundna med en kant, såvida inte den kanten själv tillhör cykeln. Ett antihål är komplementet till ett hål. Ackordlösa grafer kan användas för att beskriva perfekta grafer — enligt den strikta perfekta grafsatsen är en graf perfekt om och bara om den inte innehåller hål och antihål med ett udda antal hörn större än tre. En ackordsgraf är en speciell typ av perfekt graf som inte har hål större än tre.
Omkretsen på en graf är längden på den minsta cykeln. Denna cykel kommer nödvändigtvis inte att ha ackord. Celler är de minsta reguljära graferna med en given vertexgrad och omkrets.
En perifer cykel är en cykel i en graf med egenskapen att vilka två kanter som helst som inte hör till cykeln kan kopplas samman med en bana vars inre punkter inte hör till cykeln. I en graf som inte bildas genom att lägga till en enda kant till en cykel måste den perifera cykeln vara en genererad cykel.
Begreppet en cykel kan också hänvisa till elementen i en grafs cykelrum. Den består av uppsättningar av kanter som har en jämn grad för varje vertex. Mängderna bildar ett vektorrum över ett ändligt fält av två element. Genom att använda metoderna för algebraisk topologi kan den generaliseras till vektorutrymmen eller moduler över andra ringar , såsom heltal, reella tal, etc. Genom Veblens sats kan vilken del av kretsloppsrymden som helst erhållas genom att kombinera enkla cykler. Cykelbasen i en graf är den uppsättning enkla cykler som utgör grunden för cykelutrymmet [2] [3] .
En oriktad graf har en cykel om och endast om djup-först-sökning (DFS) hittar en kant som leder till en redan besökt vertex (bakåtbåge) [4] . På samma sätt är alla bakkanter som DFS-algoritmen hittar en del av cykler [5] . För oriktade grafer tar det bara O ( n ) tid att hitta en cykel i en graf med n hörn, eftersom högst n − 1 kanter kan vara trädkanter.
En riktad graf har en cykel om och endast om DFS hittar en bakåtbåge. Framåtbågar och tvärgående bågar indikerar inte nödvändigtvis en cykel. Många topologiska sorteringsalgoritmer upptäcker också cykler eftersom de stör förekomsten av en topologisk ordning. Om en riktad graf är uppdelad i starkt sammankopplade komponenter existerar cykler endast i komponenterna, men inte mellan dem, eftersom cyklerna är starkt sammankopplade [5] .
Tillämpningar av loop-hittande algoritmer inkluderar väntediagram för att hitta dödlägen i system med parallella trådar [6] .
I en artikel från 1736 om problemet med sju bryggor i Königsberg , allmänt betraktad som grafteorins födelse, visade Leonhard Euler att för att en ändlig oriktad graf ska ha en sluten genomgång av alla kanter exakt en gång, är det nödvändigt och tillräckligt att den kopplas samman och har en jämn grad av alla hörn. Motsvarande beskrivning av förekomsten av en sluten genomgång av varje kant exakt en gång i en riktad graf är att kräva att grafen är starkt sammankopplad och att varje vertex har samma antal inkommande och utgående bågar. I båda fallen är den resulterande vägen känd som Euler-cykeln . Om en ändlig oriktad graf har en jämn grad av varje vertex, oavsett om den är sammankopplad eller inte, kan man hitta en uppsättning enkla cykler som täcker varje kant exakt en gång - detta är Veblens sats [7] . Om en sammankopplad graf inte uppfyller villkoren för Eulers teorem, kan en sluten genomgång av minsta längd som täcker alla kanter åtminstone en gång fortfarande hittas i polynomtid genom att lösa väginspektionsproblemet.
Uppgiften att hitta en enkel cykel som går igenom varje vertex exakt en gång, till skillnad från kanttäckning, är mycket svårare. Sådana cykler är kända som Hamiltonska cykler , och problemet med att avgöra om sådana cykler existerar är NP-komplett [8] . Många studier har publicerats på klasser av grafer som uppenbarligen innehåller Hamiltonska cykler. Ett exempel är Ores sats om att en Hamiltonsk cykel alltid kan hittas i en graf om vi, genom att addera graderna av vilket par som helst av icke-angränsande hörn, får åtminstone det totala antalet grafhörn [9] .
Den dubbla cykeltäckningsförmodan säger att för varje brolös graf finns det en multiuppsättning av enkla cykler som täcker varje kant av grafen exakt två gånger. Inget bevis på gissningarna eller motexemplet har ännu hittats [10] .
Vissa viktiga klasser av grafer kan definieras eller beskrivas av deras cykler. Det: