Content
Select a Difficulty:
10 / 35 problems visible - Upgrade to view all problems
IB: 5
10
!
0 / 6
Thomas, a train enthusiast, wants to take every major train in America. He makes a graph with vertices representing cities and edges representing train rides. Trains only go one direction, so he uses a directed graph. Each edge has weight 1.
.png?alt=media&token=3bf90ce8-d4d6-4977-aa0e-b2dffc2af80f)
- [2]
State whether there exists an Eulerian circuit for this graph. State your reasoning.
Thomas, the train enthusiast, lives in New York. Hence, he will start and end his train trip in New York.
- [1]
Find the shortest path from New York to Boston.
America Rail would like to make the graph contain an Eulerian circuit by flipping the directions of as few edges as possible.
- [2]
Find the edge that they should flip
- [1]
Find an Eulerian circuit starting with the train NY→LA.
11
!
0 / 6
The weights of edges in a graph are given in the table below:
- [2]
Using Kruskal's algorithm, find the minimum spanning tree of the graph.
- [2]
Using Prim's algorithm, find the minimum spanning tree.
- [2]
Show that the graph has no Eulerian circuit.
12
!
0 / 8
In Boston, times in minutes to get between various historical sites are given by the graph above.
- [2]
State with proof whether the graph contains any Eulerian circuits.
- [2]
Determine with proof whether the graph contains an Eulerian path.
A tour of Boston would like to take all roads between historical sites.
- [4]
Find the minimum time in which they can accomplish this.
13
!
Plus
0 / 8
14
!
Plus
0 / 4
15
!
Plus
0 / 6
16
!
Plus
0 / 6
17
!
Plus
0 / 5
18
!
Plus
0 / 4