Hamiltonian Cycle Problem

Loading...

Del curso dictado por University of California San Diego

Advanced Algorithms and Complexity

211 calificaciones

University of California San Diego

Advanced Algorithms and Complexity

211 calificaciones

Curso 5 de 6 en SpecializationData Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

De la lección

NP-complete Problems

Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.

Brute Force Search5:42

Search Problems9:44

Traveling Salesman Problem7:57

Hamiltonian Cycle Problem8:09

Longest Path Problem1:42

Integer Linear Programming Problem3:08

Independent Set Problem3:07

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Our next search problem is a Hamiltonian Cycle Problem.

The input of this problem is a graph directed on,

directed without weights and edges and the goal is just to check whether

there is a cycle that visits every vertex of this graph exactly once.

For example, for this graph, the research cycle.

It is shown here on this slide.

It is not difficult to check that it indeed, visits every vertex exactly once.

And for this reason, in general, this problem is a search problem.

Given some sequence of vertices,

it is easy to check that each vertex appears in this sequence exactly once and

that there is a match between any two consequent vertices in this sequence.

The Eulerian cycle problem looks very similar to the Hamiltonian cycle problem.

In this problem, we're given a graph again and

our goal is to find a cycle that visits every edge exactly once.

So in the Hamiltonian cycle problem,

we need a cycle that visits every vortex exactly once.

In that Eulerian cycle problem, we're looking for

a cycle that visits every edge exactly once.

It turns out that the Eulerian cycle problem can be solved very efficiently.

Namely, there is a very simple check whether the input graph is

Eulerian or not.

That is whether it contains a Eulerian cycle or not.

This is given by the following theorem.

So, it deals with undirected graph.

Assumes that way given an undirected graph and it contains a Eulerian cycle if and

only if, it is connected and the degrees of all its vertices is even.

We now give two toy examples that in particular will shut some light on how to

prove the just mentioned serum.

Our first example is a graph in which there is no Eulerian cycle,

that is a non-Eulerian graph.

There is no way Eulerian cycle in this graph in particular,

because the degree of this vertex is equal to 3.

Let's prove that it is a degree of a vertex in a graph is equal to 3 and

this graph does not have a non-Eulerian cital for sure.

First, assume as such in cycle existed and

assume that it visited this vertex, which is denoted by me.

For example, exactly once.

So, this is a cycle that visits every edge of our graph exactly once and

goes through v exactly once.

But in this case, v would have our degree exactly two.

There are two edges.

We used one of them to go out of v and

we used another of them to come back to this galaxy.

But in our case, the degree of v is equal to 3.

Now, assume that there is an Eulerian

cycle that visits the galaxy at least two times.

So, let's start our cycle from the vertex v.

So, we walk through our graph.

We get back to v and then we walk again, and then we get back to v again.

But since in our cycle we visit each edge exactly once,

in this case, we see that there are at least four edges adjacent to v.

So, which means that either the our degree of v is equal to 2 or it is at least 4.

And in general, it is not difficult to see that if we have an Eulerian cycle,

then the degree of each vertex is must be even.

Because each time when we come in to some vertex,

we need to have a match in edge, which we use to go out from this vertex.

I'm going to show an example of an Eulerian cycle in a graph and

I'll also show how to define it quickly.

This is the same graph we stood as a set of three.

And in this graph, we can see that the degrees of all vertices are even.

Namely, the degree of this vertex is 2, the degree of this vertex is 4.

This is also 4, this is 6, this is 2, this is 4.

So all of them are even and this graph is connected,

which means that this graph contains an Eulerian cycle.

Let's try to find it.

Well, for concreteness, let's start from this vertex and

let's just walk through this graph.

We first traverse this edge, then we traverse this edge,

then we get back to this, to this vertex.

At this point, we return to the vertex for which there are no more unused edges.

However, there are still some unused edges in our graph.

Let's just take and let me also mark this cycle, as the first one.

So we constructed some cycle, but still there are some unused edges.

Let's just start traversing the unused edges from some vertex.

For example, a couple from this one was in might might traverse this edge and

then again get back to the initial vertex and this is cycle number two.

In case there are still some unused cycles,

some unused edges, so let's extend, for example,

let's start from the vertex and let's traverse another cycle.

So, this is a set site we're currently constructing the third cycle.

So we go here, then here, then we get back here and then we get back here.

So at this point, we used all the edges.

However, what we have is not just one single cycle, but a bunch of cycles.

But the nice property is that if we have several cycles,

it is easily to glue them together into a single cycle.

Schematically, it can be shown as follows.

So assume that we have some cycle and we have some other cycle and

then in some other point, we have other cycle,

then what we can do is to traverse these cycles as follows.

So we first go here, then we go this way, then we go this way.

And finally, we go this way.

Let me illustrate how to do this on our example graph.

We first go on this edge, then we use this cycle,

then we continue in our first cycle,

then we triggers this cycle, the third cycle.

And finally, we get back to the initial vertex.

And this is how we, in general, an Eulerian cycle can be constructed.

We just work in the graph and when we turn back to vertex which has no unused edges,

we just start traversing another cycle from some vertex.

The fact that the initial graph is connected ensures that then

all the constructed cycles are connected to each other and

then we can glue them easily to construct a single cycle,

visiting each edge exactly once.

Let's now summarize.

We have two similarly looking problems.

In the first one in the Eulerian cycle problem,

we need to find a cycle that visits every edge of a given graph exactly once.

This problem can be solved efficiently in linear time in

the size of the input graph.

In the second problem, in the Hamiltonian cycle problem, we are looking for

a cycle that visits every vertex of our graph exactly once.

For this problem, we have no polynomial time algorithm.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2018 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play