Graph Cycle
Jump to navigation
Jump to search
A Graph Cycle is a graph path with no repeated graph edges or graph nodes, except for the start node and end node.
- …
- Counter-Example(s):
- a Simple Graph Path.
- an Acyclic Graph.
- See: Cycle Detection Task, Closed Walk, Graph Circuit, Graph Trail.
References
2013
- http://en.wikipedia.org/wiki/Cycle_%28graph_theory%29
- In graph theory, two types of object are commonly called cycles. One type of cycle, more commonly called a closed walk, consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph. The other type of cycle, sometimes called a simple cycle, circuit, circle, or polygon, is a closed walk with no repetitions of vertices or edges allowed, other than the repetition of the starting and ending vertex. Simple cycles may also be described by their sets of edges, unlike closed walks for which the multiset of edges does not unambiguously determine the vertex ordering. A directed cycle in a directed graph is a sequence of vertices starting and ending at the same vertex such that, for each two consecutive vertices of the cycle, there exists an edge directed from the earlier vertex to the later one; the same distinction between closed walks and simple cycles may be made in the directed case.
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.
A chordless cycle in a graph, sometimes called a hole, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole.
- In graph theory, two types of object are commonly called cycles. One type of cycle, more commonly called a closed walk, consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph. The other type of cycle, sometimes called a simple cycle, circuit, circle, or polygon, is a closed walk with no repetitions of vertices or edges allowed, other than the repetition of the starting and ending vertex. Simple cycles may also be described by their sets of edges, unlike closed walks for which the multiset of edges does not unambiguously determine the vertex ordering. A directed cycle in a directed graph is a sequence of vertices starting and ending at the same vertex such that, for each two consecutive vertices of the cycle, there exists an edge directed from the earlier vertex to the later one; the same distinction between closed walks and simple cycles may be made in the directed case.
2012
- http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Walks
- QUOTE: The closed equivalent to this type of walk, a walk that starts and ends at the same vertex but otherwise has no repeated vertices or edges, is called a cycle. Like path, this term traditionally referred to any closed walk, but now is usually understood to be simple by definition. In the example graph, (1, 5, 2, 1) is a cycle of length 3. (A cycle, unlike a path, is not allowed to have length 0.) Paths and cycles of n vertices are often denoted by Pn and Cn, respectively. (Some authors use the length instead of the number of vertices, however.)
- http://en.wikipedia.org/wiki/Cycle_(graph_theory)
- In graph theory, the term cycle may refer to a closed 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; see Cycle graph. A cycle in a directed graph is called a directed cycle.