Definition:Cycle (Graph Theory)
(Redirected from Definition:Closed Path)
Jump to navigation
Jump to search
Definition
A cycle is a circuit in which no vertex except the first (which is also the last) appears more than once.
An $n$-cycle is a cycle with $n$ vertices.
Subgraph
The set of vertices and edges which go to make up a cycle form a subgraph.
This subgraph itself is also referred to as a cycle.
Odd Cycle
An odd cycle is a cycle with odd length, that is, with an odd number of edges.
Even Cycle
An even cycle is a cycle with even length, that is, with an even number of edges.
Also defined as
Some sources specify a cycle as having at least one edge.
Some sources specify that a cycle must indeed have at least $3$ edges, presupposing that the graph in which it is embedded is by definition a simple graph.
Also known as
Some sources refer to a cycle as a closed path.
Also see
- Results about cycles in the context of graph theory can be found here.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.3$: Connected Graphs
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): path: 1.
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 2.3.4.1$: Free Trees
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): cycle
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): walk
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): cycle
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): walk
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): closed (in graph theory)
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): cycle (in graph theory)