All language subtitles for 21 - Hamiltonian vs Euler Paths English

This video we're going to talk about a common graph problem and we have two popular graphs called Hamiltonian

and your paths.

And I'm going to first create a very simple graph.

I'm just going to have four different nodes and they're all going to be connected by edges.

Just like that.

OK.

Now a Hamiltonian path is a path where every one of the nodes is hit at least once.

So we start here at the top.

Top left hand corner.

And we go and hit this node.

Then we go hit this node.

This one this one and then back and if we actually do go back to the middle like we did right here.

This is actually called a Hamiltonian cycle in it's a MP complete problem.

You have to work with those but that's a Hamiltonian path.

Now a Euler path and I know it looks like ular but it actually is pronounced oilor like o i l e r an

Euler path is where every one of the edges is touched at least once.

So it really doesn't care about the nodes at all but the edges are the important thing.

So if we start the same spot and we start here with this edge this age this age and this one that would

be an Euler path.

Now in this case for this type of graph the Euler path and the Hamiltonian path are the exact same.

And that's perfectly fine and it happens quite a bit.

One important thing to note is that Hamiltonian paths are empty complete where Euler paths are not.

It is pretty easy to find Euler paths and the complexity is a lot.

It is much better.

Now you may think least I thought when I originally heard this that well every Hamiltonian path and

every Euler path have to be the same right.

Because you think that if it hits has it every edge has to hit every node and vice versa.

However if you draw a different type of graph

and you draw edges on the graph here here here

here

like so then what you're going to have is a different Hamiltonian path versus an oil or path and I'll

show you how that's going to work right here.

So we'd start with the Hamiltonian all the way on the left and jump to this node node node this node

node.

Now because we need a Hamiltonian path we can only hit one node only one time.

We can't come back to this node right here.

And so if there is not a if there would not be an edge right here then the final node of the Hamiltonian

path would actually be right here which means there wouldn't really be a Hamiltonian path for this graph.

And that's a very important thing to know because knowing if there is a path is just as important as

finding it.

So that's now that's with the Hamiltonian.

Now with the Euler path though you can see it doesn't care if it visits the same node twice all it cares

about is edges.

So we would come here here here here here we could go back up to this one here and here.

So this is a valid Euler path but it is not a valid Hamiltonian path.

It's not a Hamiltonian cycle.

So this is just part of the reason why it's a lot easier to find Euler paths compared to Hamiltonian

just because mathematically it's a lot easier to find a edge is visited or it's possible to visit an

edge and also it allows for the same location the same node to be visited multiple times depending on

how many edges that it has coming to and from it.

So this is a very basic introduction to the differences between Hamiltonian versus Euler past.

Please let me know if you have any questions whatsoever.

And also in the next video.