Content
Select a Difficulty:
10 / 35 problems visible - Upgrade to view all problems
IB: 6
20
!
0 / 5
The degrees of various vertices in a graph, G, are given by deg(A)=1, deg(B)=2, deg(C)=3, deg(D)=5, deg(E)=x.
- [2]
Show that x is odd.
Suppose that the total number of edges is 10.
- [3]
Find x.
21
!
0 / 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.
- [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.
22
!
Plus
0 / 13
23
!
Plus
0 / 8
24
!
Plus
0 / 6
25
!
Plus
0 / 7
26
!
Plus
0 / 13
27
!
Plus
0 / 14
28
!
Plus
0 / 10