We now turn to studying directed graphs.

And in particular, we start with considering an important class of graphs

called DAGs, which stand for Directed Acyclic Graphs.

So just by definition, a directed acyclic graph, or

just a DAG, is a directed graph without any cycles.

So here on the slide, on the left, we see an example of a DAG.

So it is indeed a directed graph and there are no cycles in it.

On other the hand, on the right, we see a graph which is directed on one hand, but

on the other hand, there are cycles in this graph.

So, for example, this has a cycle in it, right?

So it is not a DAG.

So DAGs arise in many applications naturally.

So let me give you several examples.

So first such example is a so-called Citation Graph.

In this case, nodes represents papers.

And we have a directed edge from that paper to this paper,

if that paper cites this paper, okay?

So, in this case, it is clear that if this paper cites that paper,

then that paper was published before this paper, right?

Which basically means that when we follow a match, we go back in time.

And this ensures that, in this graph, there must be no cycles, right?

Another common graph is a [INAUDIBLE] course's Prerequisite Graph in some,

for example, computer science curriculum.

In this case, nodes are courses.

And we put a directed edge from course a to course b,

if in order to take course b, you first need to take course b, okay?

So course a is a prerequisite for course b.

And more generally, there are many such Dependency Graphs.

In the general setting, we introduce a node for any job or any item in

to-do list, for example, and then we put an edge from, say, job A to job B.

Whenever, in order to process the job B, you first need to process the job A.

So this represents the dependency between a and b.

So you cannot start processing B if you haven't yet processed the job A, okay?

So for such dependency graphs,

it is important to answer the following question.

What is the right order of processing all the jobs, one by one?

So what do I say by the right order?

I mean that we would like to [INAUDIBLE] find all the constraints.

So each time, if we had a match from A to B, then we need to make

sure that when we process the job B, then A is already processed, okay?

So, what we would like to do is, in a sense, to linearize our graph.

And first of all, it is clear that it is

definitely impossible if there is a cycle in our graph.

So if you have, for example, three jobs.

And there is a cycle between them, something like this,

then definitely it is not possible to satisfy all these constraints.

Each time, if you number these vertices, something like 1,

2, 3 and you process the jobs in this order,

of namely you first process this job, then you process this job and

then you process this job, then it will be allayed this constraint, okay?

So, because this constraint says that when you start processing the job one,

you only need to do this after you already processed the job three.

But this constraint is varied, in this case.

So if there is a cycle, then definitely this is not possible.

We do not expect titles in dependency graphs, okay?

On the other hand, it turns out that if there is no cycle,

then such an ordering is always possible.

And in fact, it is not so difficult to construct this ordering.

Okay, well, we'll prove it in a minute, but first,

let me introduce this notion formally.

So we say a Topological Ordering of a graph,

or the topological ordering of a set of vertices of this graph,

is an ordering satisfying all the edge constraints.

Namely, whenever there is an edge from u to v,

then u goes before v in this ordering.

Let me show you an example.

Now in this case, we have five nodes in our graph.

And on the right, we have this ordering.

As you see,

the ordering can be specified just by placing all the nodes just in a line.

In this case, we say that some node goes before

some other nodes in our ordering, if it is placed to the left of that node, right?

So what you see is that if we place all the nodes on the line, and then if we draw

all the edges in our graph, then all of them most go from left to right.

In this case, we say that this is a valid topological ordering.

As we've just discussed on the previous slide, if there is a cycle with graphs,

then there is no topological ordering.

What we're going to prove now is that if there is no cycle,

then there exists a topological ordering.

And it not so difficult to construct it, actually.

Okay, so this is our theorem.

Every directed acyclic graph has a topological ordering.

We're going to prove it as follows.

We will show it on the next slide that every

directed acyclic graph has a sink, okay?

And a sink, by definition, is a node with no outgoing edges, okay?

This will allow us to proceed as follows.

So there is a sink in our graph, so this is a node with no outgoing edges.

This actually means that it is safe to put it through the end of our ordering.

All edges, actually only for this node, there are only incoming edges,

no outgoing edges.

So definitely from this node, there will be no conflicting edges going to the left.

Because just there are no outgoing edges for this node.

So it is safe to put it to the end of our ordering.

When we put the sink vertex to the end of our ordering,

we just remove it from our graph.

And at this point, it is important to realize that when we're moving a vertex

from an acyclic graph, we cannot add any cycle.

So it stays acyclic.

Then, in the remaining graph that we've been using,

we also extracted it and put it to the end of our current ordering and so on.

So we repeat this procedure.

Now let me illustrate this with a toy example as usual.

So consider this graph on five vertices.

In this case, there are actually two things, a and b.

Let's work and put it to the end of our ordering, so this is a.

Now we remove it from our graph, and we see that there is an edge, b.

We see that there are no outgoing edges.

So it is safe to put it to the left of a, okay?

So there will be no conflict.

Then, when we remove b, the next thing is actually c.

And you see indeed that each time when

we remove the current increment graphing, the remaining graph there is still a sink.

Probably this sink was not a sink in the previous graph when

we haven't removed the vertex.

But in any case, it is in an acyclic graph and it has at least one sink.

So in this particular graph, the sink is c.

So we put it through the [INAUDIBLE], we remove it and

now e is a sink and results in roughly with added.

And then is the remaining [INAUDIBLE], d is the only remaining vertex.

So it is definitely a sink because there are no outgoing edges for

this particular graph.

So, this is how we constructed a typological ordering.

And now what remains to be done is to show that every acyclic graph has a sink.

We will do this by assuming the contrary.

So I assume that we have some acyclic graph, but

somehow there is no sink in this graph.

This actually means that, for every node, there is at least one outgoing edge.

And this allows us to organize the following infinite work on our graph.

So just start from any node.

And since there is at least one outgoing edge from this node,

we can follow this edge.

So this will lead us to some new node.

For this node, we also know that there is an outgoing edge, and so on.

So we just start working like this, so from this node, we go to that node.

So for that node, we also know that there is at least one outgoing edge.

So we follow this edge to go to some other node.

And we repeat this process, and we can repeat this process to infinity.

However, our graph is finite, which means that, at some point,

some node is going to be repeated.

Probably not the one that we started from,

but definitely there will be a repeated node in this process.

But this, as shown by this toy example, actually constructs a cycle in our graph,

which contradicts to the fact that our initial graph is acyclic.

And which finally proves our theorem that states that every

directed acyclic graph has a topological ordering.

Directed Acyclic Graphs

Introduction to Graph Theory

Conheça os instrutores