Core: Eulerian graphs

Loading...

En provenance du cours de University of California San Diego

Advanced Data Structures in Java

917 notes

University of California San Diego

Advanced Data Structures in Java

917 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

So we're ready to talk about a slightly different graph problems, and

the hopes of maybe finding one that is tractable.

In this video, we're going to be defining an Eulerian circuit for a graph.

We'll be determining whether graphs are or aren't Eulerian, and

we'll be talking about the algorithmic questions surrounding Eulerian graphs.

Now, it's worth saying that this lesson is very abstract.

And this whole week's material really, does feel a lot more theoretical,

than what we've been doing in the courses up until now.

We're a little bit more removed from the project.

We're a little bit more removed from applications.

And there's two reasons for that.

One is that, at least I think theory is really really cool.

It's what I study, it's what I do research in, it's what I love, and so

it's really wonderful to be able to share that with you.

But the other reason is also that the theory and the concepts that we're talking

about really do end up having some very concrete applications to real problems.

And we'll actually be able to have a guest visitor tell us a little bit about that at

the end of this module, so stay tuned.

Alright but, back to Eulerian graphs and back to these somewhat abstract notions,

we talked in the previous video about Hamiltonian graphs and

Hamiltonian graphs was a graph where we could walk along all the vertices

visiting each vertex exactly once.

And so let's tweak that a little bit and we say, okay well in the graphs,

we've got vertices, we've got edges.

What if we change the definition to ask what an Eulerian graph where

we can walk along the whole graph, visiting each edge exactly once.

And so in this setting, we're allowed to visit vertices more than once.

But what we want to make sure is that each edge gets traversed exactly once.

And so let's think about some concrete graphs and

think about whether they're Eulerian and so what about this one?

Can we traverse this graph visiting each edge exactly once?

Okay, so

let's see an Eulerian path through this graph, it is in fact Eulerian.

We start at the top.

We can go around the side, and then come to that middle vertex.

Now, we wanna make sure we get that edge between the middle vertex and the top

vertex, and so we follow that edge up, and then we go back around the other side.

And so this graph is Eulerian, but notice that it's also Hamiltonian.

And the Hamiltonian path that we could take through this

graph has to be different from the tour that we just did.

And so a Hamiltonian path through this graph could just go around the periphery

and visit each vertex exactly once.

But notice that the Hamiltonian path will not traverse that middle edge.

And so it won't be a witness of being Eulerian.

All right, what about another graph?

Let's take a look over here.

Is it Eulerian?

And is it Hamiltonian.

All right, so in this graph we see that there's an Eulerian tour

through the graph.

We can start in the middle and follow all the edges in the top triangle,

then follow all the edges in one of the side triangles, and

then follow all the edges in the third side triangle.

And so we get an Eulerian graph.

But it's not Hamiltonian, because think about what that description that I gave

for the Eulerian tour just did, it had to keep coming back to the middle.

And any attempted walk through this graph that tries to visit all the vertices or

all the edges will still have to come back to that middle vertex and

that's going to be a problem with being Hamiltonian because

we're not allowed to visit any vertex more than once.

So we've got a graph here that is Eulerian, but not Hamiltonian.

One more, is this Eulerian?

All right, so you saw that this graph is not Eulerian, and

we can do an analysis that if we try to traverse any one edge, then what

we do is either we get from a periphery to the middle or the middle to the periphery.

If we went from the middle to the periphery then we'd be stuck.

We'd be at a periphery vertex with no way of getting back

other than going along an edge that we've already traversed.

Bad news.

If we went from the, from a periphery vertex to the middle vertex,

at the beginning then we could have one more hop from the middle to a periphery,

but then there's one edge and one vertex that we won't have traversed.

And so, there's not going to be any Eulerian to work through this graph, and

similarly no Hamiltonian path through this graph, as we saw in the previous video.

All right, one last example.

It's really useful to see all the different combinations that we can get,

and so in this graph we saw before that it is a Hamiltonian graph and is it Eulerian?

Okay, so you saw in the quiz, that this is not an Eulerian graph, so

we have an example of something that's an Eulerian graph but is Hamiltonian.

The point of these four examples is to show that all possible combinations of

being Eulerian or not and being Hamiltonian or not are possible.

And so even though all we did was tweak just about that one

word in the definition, we get very, very different notions when

we're talking about Eulerian graphs and we're talking about Hamiltonian graphs.

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.

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

Télécharger dans l'App Store

Disponible sur Google Play