English subtitles

← 10-28 Combining Structures Solution

Get Embed Code
1 Language

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

  1. The answer here is that if you have n copies of this structure here in a row like this
  2. then there are 2^n different shortest paths from A to B that visit all vertices.
  3. And the reason why that is is that each time you encounter this structure here
  4. there is the two possibilities that we talked about.
  5. You can either go this way up here or you can either go this way down here
  6. and then you have to continue this way until you get to one of these edges here
  7. and then you can redecide if you want to go up or you want to go down.
  8. There's two possibilities for the first one, two possibilities for the second one,
  9. and so on and so on and so on, and two possibilities for the last one.
  10. Two multiplied by itself n times is 2^n.
  11. And this actually doesn't look too bad, does it?
  12. Because each of these gadgets, if you will, that I've drawn here could now represent
  13. a variable in a Boolean formula and each shortest path between A and B
  14. is kind of a true-false assignment to those variables.
  15. We could say for example that whenever we choose our path from A to B to go up here
  16. and then like this, this structure here or this way to do the path.
  17. Now that represents setting the variable to true so this here which represents x₁ for example
  18. so then going this way would mean x₁ is true.
  19. Going the other way, so down, would represent false.
  20. This would be a way to represent assignments of true and false
  21. to the variables x₁, x₂, and so on through xn.
  22. Now of course choosing the path between A and B is still totally arbitrary.
  23. What we are missing is the clauses of the Boolean formula.
  24. And again it takes a bit of playing around to find out how we can represent
  25. clauses here in this picture.