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

1. タイトル：
   Planar Graphs - Intro to Algorithms
2. 概説：

3. 0 0:00 - 0:04
   Another category of graphs that are very important and come up a lot are planar graphs.
4. 4000 0:04 - 0:08
   These are graphs that can be drawn in the plane on a flat piece of paper
5. 8000 0:08 - 0:11
   so that the edges don't cross.
6. 11000 0:11 - 0:13
   Here's an example of a planar graph.
7. 13000 0:13 - 0:17
   We've got five nodes and five edges.
8. 17000 0:17 - 0:21
   You see the way I drew it here. This node here and this node needed to be connected.
9. 21000 0:21 - 0:24
   I just drew a nice, little curvy line without crossing anything else.
10. 24000 0:24 - 0:29
    This is a planar graph. It still would be a planar graph even if I drew it with a crossing in it,
11. 29000 0:29 - 0:33
    because the issue is that there is some way to do it so that the edges don't cross.
12. 33000 0:33 - 0:37
    Now, in this particular example, we've got five nodes and five edges,
13. 37000 0:37 - 0:41
    but what we're interested in is what is the relationship in general between the number
14. 41000 0:41 - 0:44
    of nodes in a planar graph and the number of edges.
15. 44000 0:44 - 0:47
    This is more complicated example than any of the ones we looked at before in this unit.
16. 47000 0:47 - 0:50
    There is some kind of a relationship, and there are constraints
17. 50000 0:50 - 0:53
    by virtue of the fact that the graph is drawn in the plane.
18. 53000 0:53 - 0:56
    Let's take a look at that. Let's think about adding some edges here.
19. 56000 0:56 - 0:59
    We can add that edge. We can add this edge. We can add this edge.
20. 59000 0:59 - 1:03
    We can add this edge, and are there any more edges we can add
21. 63000 1:03 - 1:06
    while still being able to draw it in a plane? It doesn't look that way, right?
22. 66000 1:06 - 1:09
    This node is connected to all the other nodes. This one is done.
23. 69000 1:09 - 1:13
    This node is connected to three other nodes, but it can't reach this one.
24. 73000 1:13 - 1:17
    It seems like it's sort of all blocked out. That's going to be true in general.
25. 77000 1:17 - 1:20
    There's going to be some graphs that can't be drawn as a planar graph.
26. 80000 1:20 - 1:24
    If we add this edge between this node and this node, the resulting graph is no longer planar.
27. 84000 1:24 - 1:26
    How many edges do we get here all told?
28. 86000 1:26 - 1:33
    We've got one, two, three, four, five, six, seven, eight, nine.
29. 93000 1:33 - 1:38
    In this example, the number of edges seems to need to be less than or equal to 9.