Connectivity, flow and routes · 32 / 53
Euler, Hamilton and TSP distinctions
Understand → trace → implement → justify
2 min reading · allow extra time for practiceEuler trails use every edge exactly once; Hamilton paths use every vertex exactly once. TSP optimises a weighted Hamiltonian tour. Delivery problems may involve edge coverage, vertex visits or vehicle routing, so model the objective precisely.
A connected undirected graph has an Euler circuit when all degrees are even; an open trail permits two odd-degree vertices. Handle isolated vertices separately. Hierholzer traverses unused edges and builds the reverse result when stuck; parallel edges need unique IDs.
Degree parity does not solve Hamiltonian existence, which is NP-complete in general. Small instances can use subset DP or backtracking; large optimisation tasks may need structure-specific methods or approximation. Euler construction and Hamiltonian enumeration have radically different costs.
A worked trace
A triangle has both tours. Two triangles sharing one vertex may have an Euler circuit but cannot visit all vertices in a Hamilton cycle without repeating the shared vertex.
Cost and assumptions
Hierholzer O(V+E); Held–Karp TSP subset DP O(n²2ⁿ) time, O(n2ⁿ) space.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
from collections import Counter
edges = [("A","B"),("B","C"),("C","A")]
degree = Counter(v for e in edges for v in e)
assert all(d % 2 == 0 for d in degree.values())
# Even degrees alone need connectivity among non-isolated vertices.TEST YOUR UNDERSTANDING
Your turn
All degrees are even in two disconnected triangles; is there one Euler tour?
Reveal the reasoning
No. All vertices carrying edges must belong to one component; parity alone is insufficient.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
Jeff Erickson · Algorithms ↗