Cycle in graph theory and computer science has several meanings:
- A closed walk, with repeated vertices allowed. See path (graph theory). (This usage is common in computer science. In graph theory it is more often called a closed walk.)
- A closed (simple) path, with no other repeated vertices or edges other than the starting and ending vertices. (This usage is common in graph theory, see "Cycle graph") This may also be called a simple cycle, circuit, circle, or polygon.
- A closed directed walk, with repeated vertices allowed. (This usage is common in computer science. In graph theory it is more often called a closed directed walk.)
- A closed directed (simple) path, with no repeated vertices other than the starting and ending vertices. (This usage is common in graph theory.) This may also be called a simple (directed) cycle.
- The edge set of an undirected closed path without repeated vertices or edges. This may also be called a circuit, circle, or polygon.
- 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 which 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 are also sometimes called graph holes. A graph antihole is the complement of a graph hole.
[edit] See also
[edit] References
