English 字幕

← 15-06 Walk Along A Tree



Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. How can we use a minimum spanning tree for shortest tour?
  2. Well there's actually one more thing we need to talk about in terms of terminology
  3. so that I can give you an algorithm for shortest tour.
  4. Then you will hopefully be able to explain to Dave as well, should he ask you.
  5. The edges are still there, but we will just look at the minimum spanning tree for now.
  6. The terminology that I would like to introduce to you is that of a walk along a tree.
  7. Of course you can define this formally, but it's actually quite easy to see.
  8. What I mean by this is if you want to do a shortest tour on a tree,
  9. then a shortest tour on a tree goes something like this.
  10. You start out at a certain vertex, and then you can travel along that tree
  11. by using every edge exactly twice.
  12. Just the way that I'm doing right now.
  13. Actually it's not possible to do it any other way.
  14. I mean of course you can walk along the tree in a different order,
  15. but actually if you want to do a walk along a tree, then you have to use every edge twice.
  16. Then of course you return back to your origin.
  17. This would be a walk along the minimum spanning tree.