Cycle

Definition

A cycle in graph theory is a path that starts and ends at the same vertex with no other vertices repeated. It forms a closed loop or circuit within the graph structure.

5 Must Know Facts For Your Next Test

1. In an undirected graph, a cycle has no direction associated with its edges.
2. A simple cycle does not repeat any vertices except for the starting and ending vertex.
3. The length of a cycle is defined by the number of edges it contains.
4. A graph containing one or more cycles is called cyclic; otherwise, it is acyclic.
5. In directed graphs, cycles are referred to as directed cycles or circuits.

Review Questions

• What distinguishes a simple cycle from other types of paths in a graph?
• How do you determine if an undirected graph is cyclic?
• What term describes the presence of cycles in directed graphs?

Related terms

Path: A sequence of edges connecting a sequence of vertices without repeating vertices.

Circuit: Another term often used interchangeably with 'cycle,' specifically in directed graphs.

Acyclic Graph: A graph that contains no cycles.