MATH367 Specimen Class test I
Problem 1: Tree graphs and planar graphs
1. Describe tree graphs that correspond to the Prüfer sequence P = (2, 3, 4,..., n−2, n−1), with n some positive integer number. (3 points)
2. Prove that any tree graph is a planar graph (2 points) .
3. Prove that we obtain a planar graph by adding one more edge to any tree graph (without changing the number of vertices) (2 points) .
Problem 2: Eulerian and Hamiltonian graphs
1. Construct an Eulerian trail for the following graph: (4 points)
2. Which tree graphs are Hamiltonian graphs? (2 points)
Problem 3: Minimal spanning trees and shortest-distance paths
Consider the following network N :
N consists of four vertices {s,a,b,t} and ve edges {{s,a} , {s,b} , {a,t} , {b,t} , {a,b}} with the weights wt({s,a}) = 1, wt({s,b}) = 2, wt({a,t}) = 3, wt({b,t}) = 4, wt({a,b}) = −7.
1. List all cycles of N and their weights. (2 points)
2. Apply the Prim's (2 points) and the Kruskal's (2 points) algorithms to nd the minimal spanning tree of N. Apply Dijkstra's algorithm to nd the shortest path between the vertices s and t (2 points) . If some of these algorithms are not applicable to the network N , explain why.
Problem 4: Assignment problem
Two workers W1 and W2 are capable of performing n1 = 1 and n2 = 2 tasks, respectively. They need to accomplish as many tasks as possible out of the four tasks T1 , T2 , T3 and T4 . Each task can be accomplished by one worker only. The cost of performing the task Tj by the worker Wi is given in the table below:
Use a cost ow network to nd out how to accomplish the maximal pos- sible number of tasks at the least possible cost. (7 points) Discuss whether your assignment is unique and justify your answer. (2 points)