Hello and welcome to the next lesson of the graph class devoted to connected components.

To motivate the study of connected components of graphs,

let's consider the following two seemingly unrelated puzzles.

The first one is called The Heaviest Stone.

The setting in this puzzle is the following: we are given n stones.

And we have an expert who is going to convince us that

some of these n stones is the heaviest one.

For this, she is going to use pan balance.

Mainly, at each iteration, she is going to take two stones

and to put them on the pan balance,

and the pan balance will show that, for example in this case,

this one, this stone is heavier than that one.

So the question is, What is the minimum number of size comparisons needed to convince

everybody that some particular stone is indeed the heaviest one?

The next puzzle is the puzzle that you've seen already.

It is called Guarini puzzle and in this case,

the question is the following: We're given a three by three board,

in which in one setting we have two white knights at the top row

and two black knights at the bottom row.

And the question is whether it is possible to move the knights

to actually swap the knights finally,

and to get two black knights at the top row and two white knights at the bottom row.

And we know already that this is indeed possible, right?

On the other hand, we know already that the initial configuration is such

that we have white knight here and black

knight here and also black knight here and white knight here,

and we would like to reach a situation where we have two black knights at the top row,

and two white knights at the bottom row, then this is, in fact, impossible.

So we've actually shown this by analyzing the corresponding graph.

But the question now is whether it is possible

to implement a simple program that will check this for us,

so instead of trying to understand whether some configuration

is reachable from some other manually, we would like to do this automatically.

So these are two seemingly unrelated puzzles,

but as you might have already guessed,

we will show that both of them can be solved by

analyzing the connected components of some underlying graph.

Now let me switch to define the connected components.

For this first, consider the following maze.

Now, in this case, it is just simply a grid with

walls between some of the neighboring cells.

Now, it is not so difficult to see that, in this case,

there are three connected regions shown here in red, blue, and green.

And by saying that some region is connected,

we mean that any cell is reachable from any other cell.

So any green cell is reachable from

any other green cell and the same for blue region and the same for red region.

On the other hand,

all these three regions are different,

meaning that if we're given a cell in a blue region, for example,

then we cannot reach a cell in a green region.

And, of course, there is also an underlying graph in this case.

So to show this, let's introduce a node for every cell in our maze.

Now let's connect, by edges, any two neighboring cells,

such that there is no wall between them.

This will give us the following graph shown here on the slide.

Now let's forget about the initial maze and let's just focus on this graph.

Again, it is not so difficult to see that this graph consists of

three connected components and

these connected components are essentially the same as were in our maze.

So let me now try to formalize this notion and let me

also specify that in this video we are working with undirected graphs.

So, for such a graph, we say that two vertices, u and v, are connected

if there is a path between u and v.

Then, first of all, it is not so difficult to see that this binary relation,

to say it formally, is transitive.

This means that if u and v are connected, and v and w are connected,

then u and w are also connected.

Well, intuitively this is clear.

Let me try to show this.

So, if we have u and v, vertices u and v,

so they are connected,

which means that there is some path in a graph.

If, on the other hand, v and w are also connected,

this also means that there is a path

somewhere in our graph that connects v and w. But if you join these two paths,

this will give you a path from u to w,

which means that u and w are also connected.

And also we say that the graph is connected

if there is a path between any of its two nodes.

So, in this case, it cannot be disconnected into two independent parts.

There is a path between any two nodes.

Awesome!

Now, we are ready to define connected components, formally.

So connected components of the graph are just connected parts of your graph.

So, formally, we say that any graph can be partitioned, more formally,

vertices of any undirected graph can be partitioned into

parts called connected components,

satisfying the following properties.

First of all, each node of your graph belongs to exactly one connected component.

Also, each connected component is connected,

meaning that for every two vertices

of a connected component, there is a path between them.

And also different connected components are disconnected from each other,

meaning that if you have a node in one connected component

and a node in another connected component,

then there is no path in the graph between them.

Let me now show you a small example.

In this case, we have five nodes and there are no edges,

so initially every node forms a separate connected component,

or the number of connected components is equal to five.

Then, if we add these two edges to our graph,

then the number of components drops to three.

So, the first three nodes form a connected component

and the fourth vertex forms a separate connected component,

and the last vertex also forms a separate connected component.

Finally, if we add two more edges, then the graph becomes connected,

so, in this case, the number of components is just equal to one.