Cycle (graph theory)
In graph theory, two types of object are commonly called cycles. One type of cycle, more commonly called a closed walk, consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph. The other type of cycle, sometimes called a simple cycle, circuit, circle, or polygon, is a closed walk with no repetitions of vertices or edges allowed, other than the repetition of the starting and ending vertex. Simple cycles may also be described by their sets of edges, unlike closed walks for which the multiset of edges does not unambiguously determine the vertex ordering. A directed cycle in a directed graph is a sequence of vertices starting and ending at the same vertex such that, for each two consecutive vertices of the cycle, there exists an edge directed from the earlier vertex to the later one; the same distinction between closed walks and simple cycles may be made in the directed case.
The term cycle may also refer to:
- An element of the binary or integral (or real, complex, etc.) cycle space of a graph. This is the usage closest to that in the rest of mathematics, in particular algebraic topology. Such a cycle may be called a binary cycle, integral cycle, etc.
- An edge set that has even degree at every vertex; also called an even edge set or, when taken together with its vertices, an even subgraph. This is equivalent to a binary cycle, since a binary cycle is the indicator function of an edge set of this type.
A chordless cycle in a graph, sometimes called a hole, 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 of a graph hole.
An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge). Equivalently, all the back edges, which DFS skips over, are part of cycles. In the case of undirected graphs, only O(n) time is required, since at most n − 1 edges can be tree edges (where n is the number of vertices).
A directed graph has a cycle if and only if a DFS finds a back edge. Forward and cross edges do not necessarily indicate cycles. 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 components, cycles only exist within the components and not between them, since cycles are strongly connected.
- Euler cycle, a closed walk containing every edge exactly once.
- Hamiltonian cycle, a cycle containing every vertex.
- Chordal graph, a graph without induced cycles of length more than three.
- Bipartite graph, a graph without odd cycles.
- Perfect graph (or a Berge graph), a graph without odd hole and without odd antihole.
- Girth, the length of the shortest cycle in a graph.
- Balakrishnan, V.K. (2005). Schaum's outline of theory and problems of graph theory ([Nachdr.]. ed.). McGraw-Hill. ISBN 978-0070054899.
- Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings". Applied Combinatorics (5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.
- Sedgewick, Robert (1983), "Graph algorithms", Algorithms, Addison-Wesley, ISBN 0-201-06672-6
- Silberschatz, Abraham; Peter Galvin, Greg Gagne (2003). Operating System Concepts. John Wiley & Sons, INC. p. 260. ISBN 0-471-25060-0.