Showing Revision 2 created 05/25/2016 by Udacity Robot.

1. タイトル：
   Eulers Formula - Intro to Algorithms
2. 概説：

3. 0 0:00 - 0:02
   Let's take a look at Euler's formula again.
4. 2000 0:02 - 0:06
   What we're going to do is prove by induction that this holds.
5. 6000 0:06 - 0:11
   We can build any planar graph by iteratively adding nodes and edges.
6. 11000 0:11 - 0:15
   Let's start off with the simplest thing, which is just a single node. Ta-da!
7. 15000 0:15 - 0:19
   We can start off with just the simplest graph of all--just a node sitting on the plane all by itself,
8. 19000 0:19 - 0:23
   a lonely point, and we've got one node, no edges, and one giant region around it,
9. 23000 0:23 - 0:26
   and 1 - 0 + 1 is indeed 2.
10. 26000 0:26 - 0:28
    That's our base case.
11. 28000 0:28 - 0:30
    Now we proceed by induction.
12. 30000 0:30 - 0:32
    Given that we're doing a proof by induction, we're going to assume that we have
13. 32000 0:32 - 0:36
    some planar graph and that Euler's formula holds for that graph.
14. 36000 0:36 - 0:41
    We have already that n - m + r = 2.
15. 41000 0:41 - 0:45
    What we're going to do is we're going to add to this graph so that it's still planar
16. 45000 0:45 - 0:47
    and see what happens to this formula.
17. 47000 0:47 - 0:49
    There are two different ways that we can add to this graph.
18. 49000 0:49 - 0:53
    We can add a node and an edge together, or we can add an edge between two exiting nodes.
19. 53000 0:53 - 0:56
    Let's consider this first case where we had a new node and an edge between them,
20. 56000 0:56 - 0:59
    and it's still a planar graph. What happens to m, n, and r?
21. 59000 0:59 - 1:02
    Well, we have one new node and one new edge but the number of regions hasn't changed.
22. 62000 1:02 - 1:05
    We're just jutting into some region inside or outside,
23. 65000 1:05 - 1:10
    but it doesn't change the total number of regions--(n + 1) - (m + 1)--
24. 70000 1:10 - 1:15
    these ones cancel, and we get n - m + r,
25. 75000 1:15 - 1:17
    which by our inductive hypothesis we said is 2.
26. 77000 1:17 - 1:20
    In that case, the formula still holds.
27. 80000 1:20 - 1:22
    What about the case where we just add an edge.
28. 82000 1:22 - 1:24
    One way we can add an edge is inside of some other region,
29. 84000 1:24 - 1:26
    and let's look what happens in that case.
30. 86000 1:26 - 1:30
    The number of nodes is unchanged. The number of edges has gone up by one.
31. 90000 1:30 - 1:33
    But the number of regions has gone up by one as well.
32. 93000 1:33 - 1:35
    This used to be one giant region, and it's now been split in to two regions.
33. 95000 1:35 - 1:38
    Once again, these ones cancel.
34. 98000 1:38 - 1:40
    Our formula still holds.
35. 100000 1:40 - 1:42
    Let's just double-check what happens if we do something on the outside,
36. 102000 1:42 - 1:45
    sort of breaking into the huge vast region around it.
37. 105000 1:45 - 1:47
    Connect, say, these two nodes, what have we done?
38. 107000 1:47 - 1:50
    We still have the vast region around it, but we created a new region here.
39. 110000 1:50 - 1:52
    Again, the number of regions has gone up by 1.
40. 112000 1:52 - 1:56
    Similarly, if we click this over the number of regions has gone up by 1.
41. 116000 1:56 - 2:00
    If we add an edge without a corresponding node, the number of regions goes up by 1.
42. 120000 2:00 - 2:03
    If we add an edge and a node together, the region stays the same,
43. 123000 2:03 - 2:06
    but the number of nodes goes up by 1.
44. 126000 2:06 - 2:10
    No matter what you do, this formula keeps holding. Pretty cool.