Algorithms On Networks

Question 0

Be able to describe Prim’s algorithm.

Answer 0

See notes of p45 of D1.

Question 1

Be able to describe Kruskal’s algorithm.

Answer 1

See notes/p41 D1

Question 2

Prove that there must always be an even number of verticies with odd valency in every graph.

Answer 2

Each arc has two ends and so will contribute two to the sum of the valencies of the whole graph.

The sum of the valencies = 2 x number of arcs
The sum of the valencies is even
Any odd numbers must occur in pairs
There is an even number of odd valencies

Question 3

Be able to describe the route inspection algorithm.

Answer 3

Identify any valencies with odd valency.
Consider all possible complete pairings of these verticies.
Select the complete pairing that has the least sum.
Add a repeat of the arcs indicated by this pairing to the network.