3.16 Graph algorithms: trees, cycles and routes Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
14 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 14 cards
- Difference between a trail and a path?
- A trail has no repeated edge; a path has no repeated vertex.
- Difference between a circuit and a cycle?
- A circuit is a closed trail (vertices may repeat); a cycle is a closed path (no repeated vertices).
- When does a connected graph have an Eulerian circuit?
- When every vertex has even degree.
- When does a connected graph have an Eulerian trail but no circuit?
- Exactly two vertices of odd degree; the trail starts at one and ends at the other.
- What is a Hamiltonian cycle?
- A cycle that visits every vertex exactly once and returns to the start.
- How many edges does a tree with vertices have?
- .
- State Kruskal's algorithm.
- Add the smallest edge that does not form a cycle, until edges are chosen.
- State Prim's algorithm.
- Start at a vertex; repeatedly add the cheapest edge joining the tree to a vertex outside it.
- How is Prim's matrix method carried out?
- Delete the start row and circle its column; choose the smallest uncrossed entry in circled columns; delete that row, circle its column; repeat.
- What does the Chinese postman problem find?
- The shortest closed route that traverses every edge at least once.
- How do you solve Chinese postman with four odd vertices?
- Find the three pairings, use least distances, repeat the pairing with least total; add it to the total edge weight.
- What does the nearest neighbour algorithm give for the TSP?
- An upper bound on the length of the shortest Hamiltonian cycle.
- What does the deleted vertex algorithm give?
- A lower bound: MST of the remaining graph plus the two shortest edges at the deleted vertex.
- Why complete a table of least distances?
- The TSP needs a complete graph; the table gives the shortest distance between every pair of vertices.