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.