Minimum Spanning Trees and P vs NP

(a) Draw two different minimum spanning trees for the graph below. 4 4 8 8 6 In your answer show the final trees including the weights on the links of the trees. [6 marks] b) What does it mean to say that a problem is not in NP? Give an example of a problem that is not in NP. (c) Briefly describe how a problem can be shown to be NP-Hard. (d) What was the first problem shown to be NP complete? [4 marks] [3 marks] [1 mark]