Eulerian Cycles: Criteria

Loading...

From the course by University of California San Diego

Introduction to Graph Theory

213 ratings

University of California San Diego

Introduction to Graph Theory

213 ratings

Course 3 of 5 in the Specialization Introduction to Discrete Mathematics for Computer Science

We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. In this course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible! By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

From the lesson

CYCLES

We’ll consider connected components of a graph and how they can be used to implement a simple program for solving the Guarini puzzle and for proving optimality of a certain protocol. We’ll see how to find a valid ordering of a to-do list or project dependency graph. Finally, we’ll figure out the dramatic difference between seemingly similar Eulerian cycles and Hamiltonian cycles, and we’ll see how they are used in genome assembly!

Eulerian Cycles4:09

Eulerian Cycles: Criteria11:44

Hamiltonian Cycles4:17

Genome Assembly12:51

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering

So the Eulerian theorem states that a connected graph,

a connected, undirected graph has an Eulerian cycle, if and

only if all the degrees of all its nodes are even, okay?

For the directed case, the theorem states that a strongly connected

graph has an Eulerian cycle, if and only if all its nodes are balanced.

And by saying balanced, we mean that the in-degree of each

node is equal to its out-degree, okay?

So some part of this theorem, of these two criterias, are actually easy to see.

So if we have, for example, let's focus on the directed case.

If we have a cycle that visits all the edges of the graph and

then enters the same vertex and the same node, this actually means that for

each node, the number of times we enter this vertex

was the same as the number of ways we lapped this vertex, right?

Which means that its in-degree must be equal to its out-degree.

So once again, if there is an Eulerian cycle,

then every node in this graph should be balanced.

The difficult part, the not-so-obvious, let me say so part, is the opposite part.

So what we need to show is that if all the degrees are balanced,

then there is an Eulerian cycle.

And this is exactly what we are going to do now.

So we will focus on the directed case.

So as we've just discussed,

if some node is imbalanced then definitely there is no way an Eulerian cycle.

So what we're going to show now is that if each node is balanced,

then there is an Eulerian cycle.

And this is exactly the graph shown here on the slide.

You can check that for every node here its in-degree is equal to its out-degree.

For example, for a we have exactly one incoming edge and

exactly one outgoing edge.

For the node d, for example, we have two incoming edges.

Let me show them.

So these are two incoming edges and two outgoing edges, okay?

And the same for the vertex h, we have two incoming edges.

And two outgoing edges.

Okay, so this graph is balanced and

our goal is to construct an Eulerian cycle in it, okay?

What we're going to do is just to go for a walk in this graph.

Let's start walking from some node and in this case, let's start walking from a.

So, we walk from a to b, and then we walk from b to c.

So since our graph is balanced,

when we enter some node, we always have a place ability to leave this node.

This is just because the number of incoming edges to any node is

equal to the number of outgoing edges.

So what will happen during this walk is that at some point,

we will get out of edges, right?

So at this point, we return back to a and there are no untraversed edges.

Yes, let me also mention that of course,

we are only going to traverse edges that haven't been traversed previously.

Okay, so at this point it seems that we are stuck.

We returned to the node a,

there are no untraversed edges connected to a on one hand.

And on the other hand unfortunately, we haven't yet constructed an Eulerian cycle,

so we are just stuck at a vertex a.

At the same time note that at this point, we just have a cycle.

And also we do remember that our graph is strongly connected.

This means that there should be at least one node

on our cycle which is connected to the rest of the graph.

More precisely, there must be a node in our cycle for

which there are outgoing untraversed edges.

So in our case, one of such nodes is actually the node c.

And also note at the same time that now we have a cycle.

And for the cycles, there is no beginning and no end, right?

So we can start traversing this cycle from any of its nodes.

For example, let's assume that

we've started to traverse this cycle from the node c, okay?

And it's convenient because we can, on one hand, for

C, there is still some outgoing untraversed edges.

At the same time, we're going from c,

we can easily traverse the cycles that were constructed previously.

We started from c, and we end at c, and then we continued to traverse this, right?

This way, by shifting the starting point of our cycle,

we actually make sure to glue same two cycles.

So I will tell about this more in a minute.

So let's continue traversing our graph from the node c.

So we go from c to d.

We go from d to g and from g to c.

And now we are again stuck at the vertex c.

Okay, let's now see what happened.

On our first iteration, we started from node a and we constructed some cycle.

Okay, this was, very roughly, this is how our cycle looked like.

Then we realized.

So this was vertex a.

Then we realized that in our cycle somewhere there is a vertex c for

which there were some untraversed edges.

And we found some other cycle, okay?

But then through this node c we can glue these two cycles, right?

Because now, we can traverse these two cycles starting from the vertex c.

So we start from here, we traverse the first cycle this way, and

then we traverse this cycle this way.

So this way, we actually get a larger cycle, okay?

We first constructed some cycle, and

then we actually extended by including some additional cycle.

And what we get now is still some cycle that visit some edges.

And there is still not an Eulerian because there are still untraversed edges.

But now, we're going to repeat the same procedure.

Now we have a larger cycle and in this cycle,

there is a vertex g, which still has untraversed edges.

So we might assume that our brown cycle here,

we started to traverse it from g and we traverse all the brown edges.

And then we continue exploring the graph.

So we go from g to h.

And then we get back to g from h.

Now we extended our cycle even further.

And then we continued from the vertex d, which lies in our brown cycle on one hand.

On the other hand, it still has some outgoing untraversed edges.

And this way, we extend our cycle finally to an Eulerian cycle, okay?

And this basically proves our theorem for, for the directive case, okay?

Now the remaining question is, what happens with path instead of cycles?

It is actually not so difficult to reduce this criteria to the criteria

of the existence of Eulerian cycles.

First of all, if we are looking for a path in our graph, then of course,

not every vertex, not every node in every graph should be balanced because for

the path, we have one outgoing edge.

Probably we visit this node once more again.

This basically means that for the starting vertex of our path,

it has outgoing out-degree which is one more than its incoming degree.

And the same is for the end of this path, right?

Then if you would like to get the criteria,

first of all in your graph if there is an Eulerian path,

then these two vertices should be uniquely definable and identifiable.

There should be a vertex whose out-degree is one times larger than

its out-degree and vice versa for its end vertex, it should be a uniquely

defined vertex whose in-degree is one larger than its out-degree.

But if you add a match from this ending point to its starting point and

then you will get a cycle.

And basically then you can use a criteria form for cycles.

Let me illustrate this on this simple example.

So, imagine the following graph.

So, in this case the in-degrees and out-degrees are as shown on this slide.

So for example, for this vertex, its in-degree is equal to 2 and

out-degree is also equal to 2.

This vertex is also balanced, and this vertex is balanced.

On the other hand, for this vertex we have in-degree equal to 1 and

out-degree equal to 2, which means that this Is the only

vertex that can be a starting vertex of another impasse.

On the other hand, for this vertex its in-degree is equal to 2, but

its out-degree is equal to 1, which means that it is exactly the vertex

that should be the last vertex of an Eulerian path, okay?

Now, let me try to construct the corresponding Eulerian cycle here.

We might, for example, go first here,

then here, then here, then here,

then here, here, here, okay?

So indeed, there is an Eulerian path in this graph.

And particularly, we would like just to find the simple criteriaism.

It remains to note that if we add the following edge from the uniquely

determined end of the path to the uniquely determined beginning of the path,

then what we get is actually an Eulerian cycle in the resulting graph.

And for an Eulerian cycle, we all ready have a criteria.

So a criteria for a path in a directed graph is the following.

So there should be a uniquely determined beginning of the path.

There should be a uniquely determined end of the path.

Such that if you add a match between them,

then the graph should become balanced, okay?

Okay, finally, let me mention, let me conclude this video with mentioning that

the method, actually, that we use to prove that there is an Eulerian path to

this graph can be easily transformed into a program or into an algorithm.

And indeed, for this program for finding Eulerian cycles or

path in the graph, they're very efficient algorithms in practice.

So even if in your graph there are millions of edges and millions of nodes.

It is very easy to find an Eulerian cycle just in the blink of an eye.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play