English 字幕

← 01-05 Eulerian Path Solution

埋め込みコードを取得する
3言語

Showing Revision 1 created 06/27/2012 by Amara Bot.

  1. All right. Let's look at the answer.
  2. Here's a particular graph where all the nodes are of even degree.
  3. Let's see what happens when we try to follow an Eulerian path.
  4. Let's just pick any node to start--say E--and go to C.
  5. There are some choices here. Let's follow an edge back to B.
  6. Then maybe to D to C to A to B and to E.
  7. So it looks like we were able to hit all of the edges exactly once.
  8. This graph does have an Eulerian path.
  9. But there's something very special about that path,
  10. and that it is started at E and it ended with E.
  11. Because the path actually started and ended at the same node,
  12. that node should have even degree,
  13. because each time we go into we come out,
  14. except for the first time where we go out but then the last time we come back in.
  15. Everything matches up and you end up with even degree.
  16. This is a special kind of Eulerian path called an "Eulerian Tour."
  17. "To tour" in the sense that we start off in our home city,
  18. and we go around, we visit lots of things, and we come back to our home city.
  19. We kind of did a tour of the graph, and it was very scenic.
  20. That's an Eulerian Tour.
  21. This first answer is definitely not correct.
  22. Such a graph can have an Eulerian path.
  23. No, it doesn't depend on the graph.
  24. It turns out that this is going to be fine no matter what,
  25. because we're going to end up starting and ending at the same node.
  26. We could have actually started and ended on any of the nodes
  27. and it would've worked out the same way. All such graphs do.
  28. All graphs that have only even degree nodes do have Eulerian paths,
  29. specifically Eulerian Tours, but it's not the case that all such graphs do.
  30. Let's make a quick example graph just so that you can see it.
  31. For this to work we need to have a graph where more than two of the nodes has odd degree.
  32. Let's make one where four of the nodes has odd degree.
  33. We have these four nodes--F, G, H, and I.
  34. Let's make it so that each of them has odd degree.
  35. Now they all have even degree. Now two of them have odd degree.
  36. If we connect these two guys, then they have odd degree as well.
  37. All the nodes have odd degree. It's not just 0 or 2.
  38. All of them have degree of 3.
  39. Let's see what happens when we try to make an Eulerian path.
  40. We'll pick some node like I.
  41. We'll go I to G, G to F, F to I, I to H, H to F, and now we hit a dead end.
  42. Maybe we didn't want to do that. Let's instead go H to G where we also hit a dead end.
  43. In fact, you can do this all day long, and what you're going to discover
  44. is there's always going to be at least one edge that you just can't visit,
  45. because again, each node in this case has an odd degree.
  46. Every part of the path has to come into the node and out of it,
  47. so it has to have even degree except for the endpoint.
  48. No matter what we're going to be stuck.