Editing Cycle (graph theory)

{{Short description|Trail in which only the first and last vertices are equal.}}
[[File:Graph cycle.svg|thumb|A graph with edges colored to illustrate a [[Path (graph theory)#Walk, trail, and path|closed walk]], H–A–B–A–H, in green; a circuit which is a closed walk in which all edges are distinct, B–D–E–F–D–C–B, in blue; and a cycle which is a closed walk in which all vertices are distinct, H–D–G–H, in red.]]

In [[graph theory]], a '''cycle''' in a [[Graph (discrete mathematics)|graph]] is a non-empty [[Path (graph theory)#Walk, trail, and path|trail]] in which only the first and last [[Vertex (graph theory)|vertices]] are equal. A '''directed cycle''' in a [[directed graph]] is a non-empty [[Path (graph theory)#Directed walk, directed trail, and directed path|directed trail]] in which only the first and last vertices are equal.

A graph without cycles is called an ''acyclic graph''. A directed graph without directed cycles is called a ''[[directed acyclic graph]]''. A [[connected graph]] without cycles is called a ''[[Tree (graph theory)|tree]]''.

== Definitions ==
=== Circuit and cycle ===
* A '''circuit''' is a non-empty [[Path (graph theory)#Walk, trail, and path|trail]] in which the first and last vertices are equal (''closed trail'').{{sfn|Bender|Williamson|2010|p=164}}
: Let {{nowrap|1=''G'' = (''V'', ''E'', ''Φ'')}} be a graph. A circuit is a non-empty trail {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''n''</sub>)}} with a vertex sequence {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>, ''v''<sub>1</sub>)}}.
* A '''cycle''' or '''simple circuit''' is a circuit in which only the first and last vertices are equal.{{sfn|Bender|Williamson|2010|p=164}}
* ''n'' is called the '''length of the circuit''' resp. '''length of the cycle'''.

=== Directed circuit and directed cycle ===
* A '''directed circuit''' is a non-empty [[Path (graph theory)#Directed walk, directed trail, and directed path|directed trail]] in which the first and last vertices are equal (''closed directed trail'').{{sfn|Bender|Williamson|2010|p=164}}
: Let {{nowrap|1=''G'' = (''V'', ''E'', ''Φ'')}} be a directed graph. A directed circuit is a non-empty directed trail {{nowrap|(''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''n''</sub>)}} with a vertex sequence {{nowrap|(''v''<sub>1</sub>, ''v''<sub>2</sub>, ..., ''v''<sub>''n''</sub>, ''v''<sub>1</sub>)}}.
* A '''directed cycle''' or '''simple directed circuit''' is a directed circuit in which only the first and last vertices are equal.{{sfn|Bender|Williamson|2010|p=164}}
* ''n'' is called the '''length of the directed circuit''' resp. '''length of the directed cycle'''.

== Chordless cycle ==
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|In this graph the green cycle A–B–C–D–E–F–A is chordless whereas the red cycle G–H–I–J–K–L–G is not. This is because the edge {K, I} is a chord.]]

A [[chordless cycle]] in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the [[complement graph|complement]] of a graph hole. Chordless cycles may be used to characterize [[perfect graph]]s: by the [[strong perfect graph theorem]], a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A [[chordal graph]], a special type of perfect graph, has no holes of any size greater than three.

The [[Girth (graph theory)|girth]] of a graph is the length of its shortest cycle; this cycle is necessarily chordless. [[Cage (graph theory)|Cages]] are defined as the smallest regular graphs with given combinations of degree and girth.

A [[peripheral cycle]] is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.

== Cycle space ==
The term ''cycle'' may also refer to an element of the [[cycle space]] of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the ''binary cycle space'' (usually called simply the ''cycle space''), which consists of the edge sets that have even degree at every vertex; it forms a [[vector space]] over the two-element [[finite field|field]]. By [[Veblen's theorem]], every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A [[cycle basis]] of the graph is a set of simple cycles that forms a [[basis (linear algebra)|basis]] of the cycle space.<ref name="gy">{{citation|title=Graph Theory and Its Applications|edition=2nd|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2005|isbn=9781584885054|chapter=4.6 Graphs and Vector Spaces|pages=197–207|chapter-url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155009/https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197|url-status=live}}.</ref>

Using ideas from [[algebraic topology]], the binary cycle space generalizes to vector spaces or [[module (mathematics)|modules]] over other [[ring (mathematics)|rings]] such as the integers, rational or real numbers, etc.<ref name="diestel">{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2012|chapter=1.9 Some linear algebra|pages=23–28|chapter-url=https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|access-date=2016-09-27|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204155010/https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23|url-status=live}}.</ref>

== Cycle detection ==
The existence of a cycle in directed and undirected graphs can be determined by whether a [[depth-first search]] (DFS) finds an edge that points to an ancestor of the current vertex (i.e., it contains a [[Depth-first search#Output of a depth-first search|back edge]]).<ref>{{cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=Applied Combinatorics |year=2006|publisher=John Wiley & sons|location=Hoboken|isbn=978-0-471-73507-6|edition=5th|page=49|chapter=Chapter 2: Covering Circuits and Graph Colorings}}</ref> All the back edges which DFS skips over are part of cycles.<ref name="sedgewick">{{citation | first=Robert | last=Sedgewick | author-link=Robert Sedgewick (computer scientist) | title=Algorithms | chapter=Graph algorithms | year=1983 | publisher=Addison–Wesley | isbn=0-201-06672-6 | url-access=registration | url=https://archive.org/details/algorithms00sedg }}</ref> In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only ''O''(''n'') time is required to find a cycle in an ''n''-vertex graph, since at most ''n''&nbsp;−&nbsp;1 edges can be tree edges.

Many [[topological sorting]] algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into [[strongly connected component]]s, cycles only exist within the components and not between them, since cycles are strongly connected.<ref name="sedgewick" />

For directed graphs, distributed message-based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself.
Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a [[computer cluster]] (or supercomputer).

Applications of cycle detection include the use of [[wait-for graph]]s to detect [[deadlock (computer science)|deadlock]]s in concurrent systems.<ref>{{cite book
  | last = Silberschatz
  | first = Abraham
  |author2=Peter Galvin |author3=Greg Gagne
   | title = Operating System Concepts
  | url = https://archive.org/details/operatingsystemc0006silb
  | url-access = registration
  | publisher = John Wiley & Sons, INC.
  | year = 2003
  | pages = [https://archive.org/details/operatingsystemc0006silb/page/260 260]
  | isbn = 0-471-25060-0}}</ref>

=== Algorithm ===
The aforementioned use of depth-first search to find a cycle can be described as follows:
 For every vertex v: visited(v) = finished(v) = false
 For every vertex v: DFS(v)
where
 DFS(v) =
   if finished(v): return
   if visited(v):
     "Cycle found"
     return
   visited(v) = true
   for every neighbour w: DFS(w)
   finished(v) = true

For undirected graphs, "neighbour" means all vertices connected to ''v'', except for the one that recursively called ''DFS(v)''. This omission prevents the algorithm from finding a trivial cycle of the form ''v''→''w''→''v''; these exist in every undirected graph with at least one edge.  

A variant using [[breadth-first search]] instead will find a cycle of the smallest possible length.

== Covering graphs by cycle ==
In his 1736 paper on the [[Seven Bridges of Königsberg]],<ref name = Euler>{{cite journal|last = Euler|first = Leonhard|author-link = Leonhard Euler|year=1741|title = Solutio problematis ad geometriam situs pertinentis|journal = Commentarii Academiae Scientiarum Petropolitanae|language = Latin|volume = 8|pages = 128-140 + Plate VIII|url = http://eulerarchive.maa.org/backup/E053.html}} Translated into English as [https://www.cantab.net/users/michael.behrend/repubs/maze_maths/pages/euler_en.html Solution of a problem in the geometry of position], Michael Behrend.</ref> widely considered to be the birth of graph theory,<ref>{{cite journal|last = Räz|first = Tim|year = 2018|title = Euler's Königsberg: The explanatory power of mathematics|journal = European Journal for Philosophy of Science|volume = 8|issue = 3|pages = 331–346|doi = 10.1007/s13194-017-0189-x|s2cid = 125194454| url=http://philsci-archive.pitt.edu/18320/1/main_document_philsci.pdf |quote = Arguably, the fact that Euler’s paper stands at the beginnings of graph theory is its most important innovation.}}</ref><ref>{{cite journal|last = Shields|first = Rob|author-link = Rob Shields|year = 2012|title = Cultural Topology: The Seven Bridges of Königsburg 1736|journal = [[Theory, Culture & Society]]|volume = 29|issue = 4–5|pages = 43–57|doi = 10.1177/0263276412451161|s2cid = 146875675}}</ref> [[Leonhard Euler]] proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex.<ref name = Euler/> The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be [[strongly connected]] and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an [[Eulerian path|Eulerian trail]]. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is [[Veblen's theorem]].<ref>{{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | title=An Application of Modular Equations in Analysis Situs | jstor=1967604 | series=Second Series | year=1912 | journal=[[Annals of Mathematics]] | volume=14 | issue=1 | pages=86–94 | doi = 10.2307/1967604 }}.</ref> When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in [[polynomial time]] by solving the [[route inspection problem]].

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a [[Hamiltonian cycle]], and determining whether it exists is [[NP-complete]].<ref>{{citation
 | author = Richard M. Karp
 | author-link = Richard M. Karp
 | chapter = Reducibility Among Combinatorial Problems
 | chapter-url = http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
 | title = Complexity of Computer Computations
 | editor = R. E. Miller and J. W. Thatcher
 | publisher = New York: Plenum
 | pages = 85–103
 | year = 1972
 | access-date = 2014-03-12
 | archive-date = 2021-02-10
 | archive-url = https://web.archive.org/web/20210210182452/http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
 | url-status = live
 }}.</ref> Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is [[Ore's theorem]] that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.<ref>{{citation|first=Ø.|last=Ore|author-link=Øystein Ore|title=Note on Hamilton circuits|journal=[[American Mathematical Monthly]]|volume=67|year=1960|page=55|issue=1|jstor=2308928|doi=10.2307/2308928}}.</ref>

The [[cycle double cover conjecture]] states that, for every [[bridgeless graph]], there exists a [[multiset]] of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.<ref>{{citation
 | last = Jaeger | first = F.
 | contribution = A survey of the cycle double cover conjecture
 | doi = 10.1016/S0304-0208(08)72993-1
 | pages = 1–12
 | series = North-Holland Mathematics Studies
 | title = Annals of Discrete Mathematics 27 – Cycles in Graphs
 | volume = 27
 | year = 1985| isbn = 978-0-444-87803-8
 }}.</ref>

== Graph classes defined by cycle ==
Several important classes of graphs can be defined by or characterized by their cycles. These include:
* [[Bipartite graph]], a graph without odd cycles (cycles with an odd number of vertices)
* [[Cactus graph]], a graph in which every nontrivial biconnected component is a cycle
* [[Cycle graph]], a graph that consists of a single cycle
* [[Chordal graph]], a graph in which every induced cycle is a triangle
* [[Directed acyclic graph]], a directed graph with no directed cycles
* [[Forest (graph theory)|Forest]], a cycle-free graph
* [[Line perfect graph]], a graph in which every odd cycle is a triangle
* [[Perfect graph]], a graph with no induced cycles or their complements of odd length greater than three
* [[Pseudoforest]], a graph in which each connected component has at most one cycle
* [[Strangulated graph]], a graph in which every peripheral cycle is a triangle
* [[Strongly connected graph]], a directed graph in which every edge is part of a cycle
* [[Triangle-free graph]], a graph without three-vertex cycles
* [[Even-cycle-free graph]], a graph without even cycles
* [[Even-hole-free graph]], a graph without even cycles of length larger or equal to 6

== See also ==
* [[Cycle space]]
* [[Cycle basis]]
* [[Cycle detection]] in a sequence of iterated function values
* [[Minimum mean weight cycle]]

== References ==
{{Reflist}}
* {{cite book |last=Balakrishnan |first=V. K. |date=2005 |title=Schaum's outline of theory and problems of graph theory |edition=[Nachdr.] |publisher=McGraw–Hill |isbn=978-0070054899 }}
* {{cite book |last1=Bender |first1=Edward A. |last2=Williamson |first2=S. Gill |date=2010 |title=Lists, Decisions and Graphs. With an Introduction to Probability |url=https://books.google.com/books?id=vaXv_yhefG8C }}

[[Category:Graph theory objects]]