## ← Nodes Edges Regions - Intro to Algorithms

• 2 フォロワーs
• 18 Lines

### 埋め込みコードを取得する x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=6vyrVwP2GTc" data-team="udacity"></div> ``` 3言語

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.