A graph with edges colored to illustrate path H-A-B, closed path or walk with a repeated vertex B-D-E-F-D-C-B and a cycle with no repeated edge or vertex H-D-G-H
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.[1]
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.
Chordless cycles in a graph are sometimes called graph holes. A graph antihole is the complement of a graph hole.
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).[2] Equivalently, all the back edges, which DFS skips over, are part of cycles.[3] 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.[3]
Applications of cycle detection include the use of wait-for graphs to detect deadlocks in concurrent systems.[4]
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.
References
- ^ 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.
- ^ a b 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.
