Cycle

This article is missing citations or needs footnotes. Please help add inline citations to guard against copyright violations and factual inaccuracies. (January 2008)

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 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. 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.

See also

• Chordal graph
• Induced path
• Peripheral cycle

References

This disambiguation page lists mathematics articles associated with the same title. If an internal link led you here, you may wish to change the link to point directly to the intended article.