Lesson 16

We use graph applications daily.

• Navigation.  Say, you are a fan of The Beatles and while in New York, you would like to go to Madison Square Garden from Strawberry Fields. Most likely, you will open some app on your cellphone and ask for the shortest path. This very moment you use graph algorithms! Namely, you use algorithms for finding the shortest path between two points on a map.

  



• Internet search.  When you search for something on the Internet, you also use graph algorithms. For example, the famous algorithm PageRank by Google tries to show you the most relevant pages based on your search query. To do this, it assigns a rank to every page by analyzing the hyperlinks leading to this page.

  



• Game strategies.  Graphs are often used to develop good strategies for various games. For example, in chess, one may come up with the following graph. Nodes are different game positions and there is a directed edge from one position to another one if one can get to the latter one from the former one in one move. The number of nodes in this graph is huge and the picture below shows a part of it highlighting the two most popular first moves (e2-e4 and d2-d4). For every node of this graph, one can estimate the score of the corresponding position. These scores can then be used to develop good strategies.

  



• Genome assembly.  As the first approximation, you can think of your genome as a 3-billion nucleotide long string. Biologists still have not figured out how to read the genome from the first to the last letter like we read a book. Instead, they shatter the genome into millions of small pieces and try to assemble them into contiguous chromosomes. In the Genome Assembly Problem, the goal is to assemble a genome from a collection of its short overlapping fragments called reads, not unlike assembling jigsaw puzzles. Believe it or not, but in order to solve this problem, the state-of-the-art genome assemblers use graph algorithms. We will see the main ideas later in the book.

  



• GSM.  A cellphone network usually has many stations and each of them covers an area which looks more or less like a hexagon. Roughly speaking, there are four frequency ranges and neighboring stations better use different ranges. Is it possible to assign frequency ranges to stations such that no pair of neighbors use the same one? We will see how to model this problem in terms of graphs which will in turn allows us to see four ranges are indeed always enough.

  



• Computer chips.  When producing computer chips, one naturally wants to make connections between elements of the circuit shorter. There are millions of transistors and other elements, and there are millions of connections between them and it is much cheaper to produce such circuits if the connections are short and non-intersecting. Problems like this are also solved using graph theory.