Core: Eulerian graphs, an algorithm

Loading...

Del curso dictado por University of California San Diego

Advanced Data Structures in Java

957 calificaciones

University of California San Diego

Advanced Data Structures in Java

957 calificaciones

Curso 3 de 5 en SpecializationObject 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.

De la lección

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

Conoce a los instructores

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

[MUSIC]

And so now we can ask the same question we asked before, is there

an algorithm that determines, given a graph, whether it's Eulerian or not?

And that brute force approach that we talked about before would still

work, right.

We could still generate all sequences of vertices, check whether they're paths and

check whether they're Eulerian.

And that's fine, but we talked about how it wasn't efficient.

And in fact for Eulerian graphs, there's an easier way.

And so, if we think back to our two examples of Eulerian graphs from those

just toy, basic examples, we can think about how we may have

come up with the Eulerian paths that visit every edge exactly once in these graphs.

And notice that when we were thinking about these Eulerian paths,

It was important which vertex we started with.

So for example, in the one graph,

we can't start at one of the side vertices.

We have to start in one of the two middle vertices,

because if we try to start on one of the sides, then we're gonna get stuck and

not be able to come to visit every edge.

And the algorithm is based on the observation That

when we have an Eulerian path we have to have each edge traverse exactly once and

so we can think about these edges as taking us to and from vertices.

And so what we're doing is we're partitioning all of the edges in the graph

and based on the sequence of edges that we traverse in the path and some of these

edges bring us into vertices and some of these edges take us out of vertices.

And so if we're focused on any one vertex,

in order to have an Eulerian path we have to have the same number of edges

going into that vertex as are going out of that vertex.

And so what that means is that most of the vertices in the graph need to be of

even degree in order for there to be an Eulerian path through this graph.

And We might be able to accommodate two exceptions.

Our starting vertex is allowed to have more outgoing edges than incoming edges,

and our ending vertex is allowed to have more incoming edges than outgoing edges.

And so the criterion for being is that there's, at most,

two vertices of odd degree in the graph.

And it turns out that If we have at most 2 vertices of odd degree,

then we can come up with algorithmically an Eulerian path through this graph.

Just starting at one of those odd degree vertices and

figuring out how to go from there.

And ditto If we know that our graph is Eulerian we can guarantee that it has

at most two vertices of odd degree, and so it's a really cool theoretical theorem

that you can prove about this equivalence between this notion of Eulerian and

the degree structure of the graph, and, well who cares?

One reason is that it gives us a much faster algorithm for

determining whether a graph is Eulerian but again who cares.

And the reason we care is that, A, we see the small changes in

the definition lead to really big algorithmic differences, and, B,

what that does is it gives us a direction to go.

If we're trying to use graphs to solve real world problems,

then what we want to do is model our real world problems in ways that lead

themselves to solutions via looking for Eulerian paths or looking for other graph

properties that are efficient to determine or have efficient algorithms for them.

What we notice is that, when we're looking at the theory of the graphs, that's great.

But we want to keep in mind,

when those theoretical choices lead to efficient implementations, and

those efficient implementations can help us in practice, as you'll see next.

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.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play