We conclude this lesson with discussing connected components in directed graphs.
As usual, let's start with a type of graph example.
So this graph actually looks connected,
in the sense that it is not clear how to pull it apart,
how to split it into independent parts,
like it was for undirected graphs.
On the other hand,
it is not so clear what we mean when we say that it is connected,
because there is no path, for example,
from the vertex A to the vertex C,
as you see in this graph.
Well actually there is no path from any vertex to vertex C in this graph,
because for the vertex C there are no incoming edges, right?
So it turns out that the right way of
defining connectivity in directed graphs is the following.
We say that two nodes are connected in a directed graph if there is a path
from the first of
them to the second of them and there is a path from that one to this one.
So, u and v are connected if there is a path from u to v and the path from v to u.
Taking this notion of connectivity into account, we can split,
we can partition the vertices of
any directed graph into the so-called strongly connected components,
which satisfy more or less the same properties as
connected components in undirected graphs.
Namely, each node belongs to exactly one strongly connected component.
Also, if you take any two nodes from the same strongly connected components,
then they are connected.
Let me recall what we mean by saying connected.
We mean that for these two vertices,
there is a path from, well,
let me denote them by u and v,
so there is a path from u to v and from v to u.
On the other hand,
if you take any two vertices from different connected components,
then they are not connected.
But this means in this case that there is no path either from u to v or from v to u.
Probably there is no path neither from u to v nor from v to u.
But it is not excluded that there is still a path in one direction.
So if two nodes belong to different connected components,
we only know that there are no two paths from v to u and from u to v. Let me
now illustrate the strongly connected components from the graph
that we've just seen on one of the previous slides.
In this case there are four connected components,
shown here on the slide.
So in particular the node C forms its own connected component,
as well as the node E. On the other hand,
the nodes B, H, D, I, M, A, all belong to
the same connected component and let's check that indeed.
There is a path in any of two directions between any two nodes.
For example, if we take vertex H, we can always reach the node D,
for example, and from from D we can reach B.
And on the other hand, you see that there is a cycle, right?
And also there is a cycle going through D, E, and A.
So there are two cycles having a common node.
And this basically means that any of these five vertices is
reachable from any of the other vertices in this case,
because, going through this cycle,
you can always reach B and then you can switch to the other cycle, if needed.
So, for example, if you need to go from H to A,
you first go from H to D and then you go this way.
So, indeed for any two of these five nodes,
there is a path from the first one to
the second one and there is a path from the second one to the first one.
The same holds for these three vertices,
F, G, and K. So,
they actually lie on the cycle and when there is a cycle,
then indeed all these vertices from the cycle form a connected component.
And probably there are some other nodes in this connected component.
But let me at least show that if there are two nodes lying on the same cycle,
then they lie in the same connected component.
Well, it is easy to see because from U to V there is
a path along this cycle and also from V to U there is a path along this cycle.
So whenever vertices stay on the same cycle,
they lie in the same connected component.
But as you see from this example,
it does not excluded that there as several cycles in the same connected component.
Well, in any case,
any graph can be partitioned into such connected, strongly connected components.
And actually if you contract all the vertices of
the same connected component into one vertex and if you only leave edges
that connect a vertex from
some connected component to the vertex from some other connected component,
then what you get is a graph like this is and it's usually called a metagraph.
Either metagraph or sometimes it is also called a condensation or the original graph.
It is not difficult to show that this graph is going to be a deck,
meaning that there will be no cycles in this graph.
And this is more or less clear because if there is a cycle,
as you remember them,
all the vertices should belong to the same connected component, but not different.
While in our metagraph, all the nodes correspond
different to different connected components.
So, to summarize, the nodes of any directed graph can be partitioned
into strongly connected components with the following properties.
Each node belongs to exactly one strongly connected component.
If two nodes belong to the same strongly connected component,
then there is a path from the first of them to the
second of them and from the second one to the first one.
And if the nodes belong to different connected components,
then either there is no path from the first one to
the second one in the graph or there is no path from the second one to the first one.
And probably there is just no path between these two guys or there is
just a path in one direction: either
from this one to this one or from that one to this one.
And if you contract all the strongly connected components,
if you contract each strongly connected component into one node and if you
only leave your rough edges from joining notes from different connected components,
then what you get is a metagraph or
condensation and it is known to be a directed acyclic graph.
Alexander S. KulikovVisiting Professor
