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?