Core: Hamiltonian Graphs

Loading...

En provenance du cours de University of California San Diego

Advanced Data Structures in Java

957 notes

University of California San Diego

Advanced Data Structures in Java

957 notes

Cours 3 sur 5 dans Specialization Object Oriented Java Programming: Data Structures and Beyond

How does Google Maps plan the best route for getting around town given current traffic conditions? How does an internet router forward packets of network traffic to minimize delay? How does an aid group allocate resources to its affiliated local partners? To solve such problems, we first represent the key pieces of data in a complex data structure. In this course, you’ll learn about data structures, like graphs, that are fundamental for working with structured real world data. You will develop, implement, and analyze algorithms for working with this data to solve real world problems. In addition, as the programs you develop in this course become more complex, we’ll examine what makes for good code and class hierarchy design so that you can not only write correct code, but also share it with other people and maintain it in the future. The backbone project in this course will be a route planning application. You will apply the concepts from each Module directly to building an application that allows an autonomous agent (or a human driver!) to navigate its environment. And as usual we have our different video series to help tie the content back to its importance in the real world and to provide tiered levels of support to meet your personal needs.

À partir de la leçon

Route planning and NP-hard graph problems

In this week, we'll go beyond the problem of finding a path between two points, and focus on problems requiring overall path planning. For example, if you wanted to go on errands and visit 6 different locations before returning home, what is the optimal route? This problem is actually a really well known problem in computer science known as the Travelling Salesperson Problem (TSP). Attempting to solve the problem will lead us to explore complexity theory, what it means to be NP-Hard, and how to solve "hard" problems using heuristics and approximation algorithms. We'll end the week by showing how reformulating a problem can have a huge impact: making something which was effectively unsolvable before, now solvable!

Core: Hamiltonian Graphs6:38

Core: Eulerian graphs4:42

Core: Eulerian graphs, an algorithm3:28

Core: An application in bioinformatics4:48

Rencontrer les enseignants

Leo Porter
Assistant Teaching Professor
Computer Science and Engineering
Mia Minnes
Assistant Teaching Professor
Computer Science and Engineering
Christine Alvarado
Associate Teaching Professor
Computer Science and Engineering

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

And so in the next video,

we're gonna tweak this graph problem just a little bit,

and see if maybe we can get a slightly easier graph problem to work with.

So by the end of this video you'll be able to talk about what it means for

a graph to be Hamiltonian and to determine whether, for small examples,

that particular graph is Hamiltonian.

And we'll think about algorithms for answering this question for bigger and

more systematic graphs, and we'll talk about the efficiency of that algorithm.

So let's jump in, so we were talking about the traveling salesperson problem where

our graph really represents cities and we've got N cities, one of which is our

designated hometown and we know all of the pairwise distances between the cities.

And what we like to do is find a tour that starts at hometown goes around all of

these cities and comes back home.

Now, we know that this is possible, we've talked a little bit about algorithms for

travelling sales person but what if we change it a little bit.

So for example, if now we don't care about distance so much.

But we just wanna go from one vertex, all through, all the vertices in the graph and

make sure we arrive at each vertex exactly once.

And so in the next video, we're gonna tweak

this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

And so in the next video, we're gonna tweak

this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

The question how, becomes, though, what if some edges are missing?

Many of the graphs that we're thinking about, we don't have a complete graph.

We don't have edges between every two vertices, and so

we could ask the question is there a path through the graph

that visits every vertex exactly once when our graph is a general graph?

May or may not be complete.

Now we're just going to focus on undirected graphs so

we're not worried about the directions of the edges.

So let's think about some examples and how this works.

And with each one of these, I'd like you to try thinking about whether the graph is

Hamiltonian or is not Hamiltonian and then we'll think about it together as well.

So a graph is Hamiltonian if there is such a path through the graph which visits

each vertex exactly once.

Let's look at this particular graph.

Is it Hamiltonian?

All right, we'll come back.

And so in the next video, we're gonna tweak this graph

problem just a little bit,

and see if maybe we can get a slightly easier graph problem to work with.

What we could do is we could just start at the top, and

then come towards the front, and go along the front vertices.

Then go back and go down and

go back bottom corner, and we've got a path that starts its own vertex and

visits every vertex in the graph exactly once, so this graph is Hamiltonian.

Now how about this one?

Is it Hamiltonian?

All right, welcome back.

This graph is not Hamiltonian and in order to

justify that the graph is not Hamiltonian we have to do something called little bit

more new ones than our justification that the graph is Hamiltonian.

Cuz, think about what the definitions are saying in order to prove that

graph is Hamiltonian we just need to produce this tour or

this path that goes along the graph and visits every vertex exactly once.

All right, but to prove that a graph is not Hamiltonian we have to say that no

such path exists, that no matter how we try to visit each vertex exactly once,

we're gonna fail somehow.

So, we can make that argument with this graph.

If we start in the middle vertex then we're going to have to visit one of the,

one of the periphery vertices after that and so maybe we jump up top, but then

we're stuck because we can't jump back to the middle because we already visited

the middle and Hamiltonian paths aren't allowed to visit vertices more than once.

All right, so a Hamiltonian tour can't start in the middle.

Now, could it start in the periphery?

Well, the problem with starting in a periphery is that the first step

of the path will be to have to go to the middle because the periphery

vertices just have degree one.

They're only adjacent to the middle vertex.

Then once we get to the middle we're in the same situation as before

because our Hamiltonian path would have to visit both of the periphery vertices but

we can't get from one to the other.

Other than by going back to the middle, which we can't do in a Hamiltonian path

because we've already visited the middle vertex.

Okay.

This graph is not Hamiltonian.

And, so now we've seen an example of a Hamiltonian graph and one that is not.

And then the question is how do we decide this in general?

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

How do you decide if those graphs are Hamiltonian?

And so in the next video, we're gonna tweak this

graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

And it seems a bit daunting if we have a graph that even has just hundred of

vertices, thousands of vertices, millions of vertices, to try all possible paths or

to do this reasoning about these graphs.

And so in the next video,

we're gonna tweak this graph problem just a little bit,

and see if maybe we can get a slightly easier graph problem to work with.

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

And then once we've checked that we can say is this sequence of vertices

denoting a Hamiltonian path?

Does every vertex appear exactly once?

And we could do that, we could code off of brute force implementation,

just like you've seen before in Christine's brute force implementation of

travelling salesperson.

But brute force implementations are not efficient, they're gonna take a really

long time, so is there a better way than just trying all possible paths?

Now, the piece where we verify whether a particular sequence of vertices

is a Hamiltonian path, that part was efficient.

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

And this is exactly what Leo was talking about

when he was talking about NP completeness.

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

it's a problem where we don't know of an efficient solution which, given a graph,

tells us whether there is a Hamiltonian path through that graph or not.

But if someone were to produce a candidate Hamiltonian path for us, we would be able

to check whether candidate Hamiltonian path is, indeed, a Hamiltonian path.

We're stuck with this graph question, which is a very natural graph question,

but for which we don't have an efficient solution.

So we could say what's next?

What do we do?

Are any graph problems really this hard?

We saw the travelling salesperson was hard.

We're seeing now the Hamiltonian paths are hard.

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

And so in the next video,

we're gonna tweak this graph problem just a little bit, and

see if maybe we can get a slightly easier graph problem to work with.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play