Content
[Maximum mark: 13]
.png?alt=media&token=21b14082-c24a-4a88-9d41-421d360d077b)
The graph above shows train connections to towns around a city, E.
- [2]
Show that the graph is Hamiltonian.
To earn a crown, get your answer ready before you reveal the options!
- [2]
Show that the graph has an Eulerian cycle.
The graph above shows the cost of each train line. A postman has to deliver mail to all cities.
- [5]
By using the deleted vertex algorithm, deleting F, find a lower bound for the amount of money that the postman has to pay if he takes the train.
- [3]
By using the nearest neighbor algorithm, starting at F, find an upper bound for the amount of money that the postman has to pay if he takes the train.
- [1]
Explain how one might improve these upper and lower bounds.
Ask Plex AI about this problem
Get hints, ask questions, and work through this problem step by step
I'm Plex, here to help with problems on this worksheet!