I bet you use graph applications almost every day.

Let us see some examples.

Say you are a big fan of The Beatles and while Beatles is in New York,

you want 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,

and this very moment you use graph algorithms.

You use algorithms which finds shortest path between two points on a map.

When you use Google or some other search engine,

you also use graph algorithms.

For example, the famous algorithm by Google which is called PageRank, lets you see

relevant links but almost doesn't show you your relevant pages on the Internet.

The way it works is the following:

It gives some score or rank to every page on the Internet,

so that you could see only relevant links in reply to your search grades.

Graphs are often used to develop good strategies for literally any game.

For example in chess,

you can come up with the following graph.

Vertices that correspond to different positions,

and there will be a directed edge from one position to another one

if you can get from the first position to the second one making one move.

For example, the most popular first move is either e2, e4 or d2, d4.

There are, of course, many other moves and there are many more vertices in this graph.

Here is a part of it.

And for every position using this graph,

you can estimate the score of the position and you're using these scores,

you can develop a good strategies.

In the top part of this picture you see a genome,

but the current things only allows

us to read short parts of the genome at random positions,

and given the short reads,

we want to assemble the original genome.

Believe it or not, but in order to solve this problem

of the current techniques use graph algorithms.

Later in this course, we'll see an example.

A cellphone network usually has many stations and each of them covers area,

which looks more or less like a hexagon.

Roughly speaking, there are four frequency or 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?

Well, in this case,

the case of a LAN it is possible.

We'll see why it is always possible to do so.

When you'll produce computer chips,

you want to make connections between elements of the circuit shorter.

There are millions of transistors and other elements,

and there are millions or connections between them and it's much cheaper to produce

such circuits if the connections are short and non-intersecting.

We'll see this problem later in the course.