Networks revision

How do we find the maximum flow from source to sink in a network?

• find the minimum cut

• find the shortest path

• use the Hungarian algorithm

• find the minimum spanning tree

How do we find a minimal spanning tree for a network?

• highlight the smallest available edge until a spanning tree is created

• find the shortest path from one vertex to another

• use the Hungarian algorithm

• identify the longest path from start to finish

The Hungarian algorithm is used for:

• making an allocation which minimises time or cost

• finding the shortest path between two points

• finding the minimal spanning tree

• finding the maximum flow through a network

The first 3 steps of the Hungarian algorithm, in order, are:

• column reduction, row reduction, crossing out

• crossing out, row reduction, column reduction

• crossing out, column reduction, row reduction

• row reduction, column reduction, crossing out

In an activity network, how do we find the critical path? (More than one correct answer)

• find the shortest path from start to finish

• find the longest path from start to finish

• find the activities with no slack time (float time)

• reduce the duration of an activity

What is an Euler trail?

• A journey which uses every vertex exactly once

• A journey which uses every edge exactly once

• A journey which starts and finishes at the same vertex

How do we know if a network has an Euler trail?

• there are exactly two even degree vertices

• there are an odd number of vertices

• there are exactly two odd degree vertices

• all vertices have odd degree

How do we know if a network will have an Euler circuit?

• All vertices have even degree

• All vertices have odd degree

• There are an equal number of even and odd degree vertices

What is a Hamilton path?

• A journey which uses every edge exactly once

• A journey which uses every vertex exactly once

• A journey which uses every vertex and every edge

What is Euler's rule for a connected, planar graph?

• V + F – E = 2

• E + F – V = 2

• V + E – F = 2