3.16 Graph algorithms: trees, cycles and routes

3.16 Graph algorithms: trees, cycles and routes Flashcards

IB Maths: Applications and Interpretation HL: 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 nn vertices have?
n−1n-1.
State Kruskal's algorithm.
Add the smallest edge that does not form a cycle, until n−1n-1 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.

Flashcards