Circuit
Definition
A circuit in graph theory is a path that starts and ends at the same vertex with no other repeated vertices. It is a closed loop in a graph where each edge is used exactly once.
5 Must Know Facts For Your Next Test
- A circuit must start and end at the same vertex.
- No vertices, except for the starting/ending vertex, can be repeated in a circuit.
- Every edge in a circuit is unique and used only once.
- A circuit with all vertices included exactly once is called a Hamiltonian circuit.
- Eulerian circuits traverse every edge of the graph exactly once without repetition.
Review Questions
- What distinguishes a circuit from other types of paths in a graph?
- Can a circuit contain repeated vertices? Why or why not?
- Explain the difference between an Eulerian circuit and a Hamiltonian circuit.
"Circuit" appears in:
Related terms
Path: A sequence of edges which connect a sequence of vertices.
Hamiltonian Circuit: A circuit that visits each vertex exactly once before returning to the starting vertex.
Eulerian Circuit: A circuit that traverses every edge of the graph exactly once, starting and ending at the same vertex.
