12 General Unit 4 Topic 3 2020

Which one of the following graphs is a tree?

• 
• 
• 
• 
• 

A graph has 6 vertices and 12 edges. A spanning tree for this graph will have:

• 5 vertices and 12 edges

• 5 vertices and 5 edges

• 6 vertices and 5 edges

• 6 vertices and 6 edges

• 6 vertices and 12 edges

For the graph shown here, the minimum spanning tree

has length:

• 30

• 31

• 33

• 34

• 36

There are four different human blood types: O, A, B and

AB. Blood can be donated from one human to another

using the following rules:

• Type O can donate blood to any type.

• Type AB can receive blood from any type

• Each type can donate blood to its own type.

• Each type can receive blood from its own type.

• 
• 
• 
• 

A group of five students represent their school in five different sports. The information is displayed in a bipartite graph.

From this graph we can conclude that:

• Travis and Miriam played all the sports between them.

• In total, Miriam and Fulvia played fewer sports than Andrew and Travis.

• Kieren and Miriam each played the same number of sports.

• In total, Kieren and Travis played fewer different sports than Miriam and Fulvia.

Five people are to be each allocated one of five tasks

(A, B, C, D, E). The table shows the time, in hours,

that each person takes to complete the tasks.

The total time to complete all the tasks is to be minimised. If no person can help another, Francis should be allocated task:

• A

• B

• C

• D

• E

For the flow network shown on the right, the capacity of the cut is:

• 3

• 6

• 9

• 10

The maximum flow, from source to sink, in the flow network shown to the right is:

• 10

• 11

• 12

• 13

In the flow network to the right, the weight of each edge is non-zero. The capacity of the cut shown is:

• a + b + c + d + e

• a + c + d + e

• a + b + c + e

• a + b + c − d + e

The flow network to the right shows the capacity of data flow along cables in Megabits per second.

What is the maximum flow of data, in Megabits per second, from server P to server Q?

• 20

• 22

• 23

• 24

• 30