Cycle (graph Theory)
In graph theory, the term cycle may refer 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.
Chordless cycles in a graph are sometimes called graph holes. A graph antihole is the complement of a graph hole.
Read more about Cycle (graph Theory): Cycle Detection
Other articles related to "cycle, cycles, graphs":
... An undirected graph has a cycleif 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) ...
Famous quotes containing the word cycle:
“The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.”
—Robert M. Pirsig (b. 1928)