Applications

In graph theory today people are using all kinds of graphs other than simple graphs. And there are many more ideas and techniques you have not met in this unit. There is a thing called matching where they are looking at pairing up adjacent vertices in some way. The first example of this was in World War II when the RAF had pilots and navigators available from the UK and Poland. Not all of the Poles spoke English nor did the UK pilots speak Polish. So a graph was drawn up with the pilots and navigators as vertices. Two vertices were joined if the corresponding pilots and navigators could speak the same language. Then someone tried to find the maximum number of edges that had no vertices in common. These pairings gave a flight crew for a plane. So these pairings became useful in assigning tasks in different situations.

Some graphs are called weighted graphs. They have numbers on the edges that provide information like the information on my Google map (see Motivation and History). Typically they may be routes for delivering material. For obvious reasons, you would like to be able to take the most efficient route on this graph. A lot of work has gone into this area of graph theory and there are algorithms that produce good results for small graphs. However, no one knows how to produce the best algorithm for every such graph. Indeed there is a good chance that such an algorithm doesn't exist.

The eigenvalues of an adjacency matrix are considered in spectral graph theory. These have important applications in quantum chemistry (see https://en.wikipedia.org/wiki/Spectral_graph_theory)

Graph theory is also used in gene technology. So you have caught the person who you think has committed the murder and you have genetic evidence from the scene of the crime. How can you read the genetic evidence to show that the suspect and the evidence match up? Graph theory is involved in the sequencing techniques used in this exercise (see https://plus.maths.org/content/os/issue55/features/sequencing/index). We suggest that you look up further applications. These include computer tomography, data compression, communication networks, molecular structure and so on.

Next page - Answers to questions