Graph cycle
A cycle on a graph is a path that starts and ends at the same vertex, with at least one edge and no other repeated vertices. In other words, a cycle is a closed loop in the graph.
- The length of a cycle is the number of edges it contains.
In short, a cycle is a closed loop that doesn’t visit any vertex twice (except the one it starts/ends at).
Visiting vertices and edges
- Only the starting vertex is visited twice.
- All other vertices and edges are visited exactly once.
Closed trail
A closed trail is like a cycle, but it allows vertices to be revisited, as long as no edges are repeated.
By definition, all cycles are closed trails, but not all closed trails are cycles.
flashcards
| Question | Answer |
|---|---|
| Graph cycle | In a graph, a cycle is a path that starts and ends at the same vertex, with at least one edge and no other repeated vertices (except the start/end vertex). |
| Length of a cycle | The length of a cycle is the number of edges it contains. |
| Which vertices are visited twice in a cycle? | Only the starting/ending vertex is visited twice; all other vertices and edges are visited exactly once. |
| How does a closed trail differ from a cycle in terms of vertex revisiting? | A closed trail allows vertices to be revisited, as long as no edges are repeated, while a cycle does not allow revisiting any vertex (except the start/end). |
| True or false: All cycles are closed trails. | True. |
| True or false: All closed trails are cycles. | False. |