Graph Theory Test 2 Review

Identify the path of minimum value from vertex K to vertex I in the graph below.

• KJLI

• KHJLI

• KJHI

• KHI

Determine the path of minimal value from vertex P to vertex O in the graph below.

• PQRO

• PMQRO

• PQMRO

• PNMRO

Claudia must leaver her home (Vertex C) and will then pass by each of the locations exactly once (A Hamilton Path), in order to feed all her favourite cats.

What is the minimum time in which Claudia could walk to visit all of the cats?

• 80

• 79

• 83

• 72

Gavin has some shopping to do. He will start at Tony's Tool Store (Vertex T) and will pass by each business exactly once (Hamilton Path).

Determine the minimum distance Gavin could travel to deliver his flyers.

• 19 km

• 28 km

• 24 km

• 31 km

Is the graph below a tree? If it isn't a tree, why not?

• Yes, it is a tree.

• No, because it isn't a connected graph.

• No, because a tree with 5 vertices should have 4 edges. It should also be connected, with no cycles.

• No, because a tree with 5 vertices should have 6 edges. It should also be connected, with no cycles.

Is the graph show below a tree? If not, how many edges would need to be added or removed to make it a tree?

• No, 1 edge needs to be removed

• No, 3 edges need to be added

• No, 2 edges need to be added

• No, 1 edges needs to be added

In the graph below, find the tree of maximum value.

• 
• 
• 
• 

In the graph below, determine the tree of minimum value.

• 
• 
• 
• 

If all values are in millions of dollars, determine how much it would cost to create a tree of minimum value of a city's metro system.

• $310 000 000

• $390 000 000

• $320 000 000

• 300 000 000

You would like to build an underground tunnel to connect 4 buildings in a University. Create a tree of minimum value. Draw the lines you would choose and include their value.