English 字幕

← Nodes Edges Regions - Intro to Algorithms


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

  1. To try to understand the relationship between edges and nodes in a planar graph
  2. we're going to use a result due to Euler--same Euler as before.
  3. To do that we're going to need another concept about planar graphs.
  4. Here's a planar graph on five nodes.
  5. Again, we have a notion of nodes. We have a notion of edges.
  6. We're also going to now talk about a notion of regions in a planar graph.
  7. Regions are kind of areas that are boxed off in the graph,
  8. plus the region outside of the graph.
  9. Turns out that's a really useful thing to be able to talk about.
  10. This particular graph has three regions.
  11. We'll right it's got 5 nodes, 6 edges, and 3 regions.
  12. Now, our good friend Euler discovered a fascinating relationship between these values.
  13. For any planar graph, n - m + or is equal to 2. Really?
  14. Does that work in this case?
  15. Let's check this formula with the values for this particular graph.
  16. We've got n - m, 5 -6 is -1, plus 3 is indeed 2. Interesting.
  17. We're going to figure out why that is in just a moment,
  18. but let's let you practice first understanding what these regions are.