Ingraph theory, acycle in agraph is a non-emptytrail in which only the first and lastvertices are equal. Adirected cycle in adirected graph is a non-emptydirected trail in which only the first and last vertices are equal.
A graph without cycles is called anacyclic graph. A directed graph without directed cycles is called adirected acyclic graph. Aconnected graph without cycles is called atree.
Achordless 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 thecomplement of a graph hole. Chordless cycles may be used to characterizeperfect graphs: by thestrong 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. Achordal graph, a special type of perfect graph, has no holes of any size greater than three.
Thegirth of a graph is the length of its shortest cycle; this cycle is necessarily chordless.Cages are defined as the smallest regular graphs with given combinations of degree and girth.
Aperipheral 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.
The termcycle may also refer to an element of thecycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is thebinary cycle space (usually called simply thecycle space), which consists of the edge sets that have even degree at every vertex; it forms avector space over the two-elementfield. ByVeblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. Acycle basis of the graph is a set of simple cycles that forms abasis of the cycle space.[2]
Using ideas fromalgebraic topology, the binary cycle space generalizes to vector spaces ormodules over otherrings such as the integers, rational or real numbers, etc.[3]
The existence of a cycle in directed and undirected graphs can be determined by whether adepth-first search (DFS) finds an edge that points to an ancestor of the current vertex (i.e., it contains aback edge).[4] All the back edges which DFS skips over are part of cycles.[5] 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, onlyO(n) time is required to find a cycle in ann-vertex graph, since at mostn − 1 edges can be tree edges.
Manytopological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided intostrongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.[5]
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 acomputer cluster (orsupercomputer).
Applications of cycle detection include the use ofwait-for graphs to detectdeadlocks in concurrent systems.[6]
The aforementioned use of depth-first search to find a cycle can be described as follows:
For every vertex v: visited(v) = finished(v) = falseFor 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 tov, except for the one that recursively calledDFS(v). This omission prevents the algorithm from finding a trivial cycle of the formv→w→v; these exist in every undirected graph with at least one edge.
A variant usingbreadth-first search instead will find a cycle of the smallest possible length.
In his 1736 paper on theSeven Bridges of Königsberg,[7] widely considered to be the birth of graph theory,[8][9]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.[7] The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph bestrongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as anEulerian 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 isVeblen's theorem.[10] 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 inpolynomial time by solving theroute 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 aHamiltonian cycle, and determining whether it exists isNP-complete.[11] Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example isOre'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.[12]
Thecycle double cover conjecture states that, for everybridgeless graph, there exists amultiset 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.[13]
Several important classes of graphs can be defined by or characterized by their cycles. These include:
Arguably, the fact that Euler's paper stands at the beginnings of graph theory is its most important innovation.
{{citation}}: CS1 maint: publisher location (link).