Introduction

Now that we have graphs, the world is ours. Besides telecommunication networks, roads are an obvious target for our newly-gained skills. Instead of working with a single town, we are now ready to take on a whole province, populate it with towns, and start worrying about the best way to provide connectivity from town to town through a well-thought road network.

Learning outcomes

This module will help you do the following:

• adapt a formerly encountered mathematical model to another similar situation
• employ higher-level graph-theoretical concepts (complete graph, tree, cycle, MST, Hamiltonian cycle, TSP)
• utilize an (exact, deterministic) algorithm that is efficient (belongs to the class P)
• utilize an approximation algorithm (for a hard problem that belongs to the class NP)
• combine the output of two algorithms to craft a "best of both worlds" approach

Warm-up

Warm-up assessment

In terms of optimizing the cost and the performance of a road system, multiple considerations will need to be taken into account and quantified in some numerical terms in order to compare whether one option is superior, inferior, or equal to another. Write down, in a brief paragraph, your initial throughts on what some of those criteria could be, in concrete terms: what to measure and in what units to determine how good a proposed road network structure is?

Concepts

After this module, you should be familiar with the following concepts:

• Path
• (Spanning) tree
• Cost
• Restriction
• Cycle
• Approximation

Remember that you can always look concepts up in the glossary. Should anything be missing or insufficient, please report it.