Cycle (graph theory)
In graph theory, the term cycle may refer to one of two types of specific cycles: a closed walk or simple path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle, or polygon. A cycle in a directed graph is called a directed cycle.
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.
Cycle detection 
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.
See also 
- 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.