To try to understand the relationship between edges and nodes in a planar graph
we're going to use a result due to Euler--same Euler as before.
To do that we're going to need another concept about planar graphs.
Here's a planar graph on five nodes.
Again, we have a notion of nodes. We have a notion of edges.
We're also going to now talk about a notion of regions in a planar graph.
Regions are kind of areas that are boxed off in the graph,
plus the region outside of the graph.
Turns out that's a really useful thing to be able to talk about.
This particular graph has three regions.
We'll right it's got 5 nodes, 6 edges, and 3 regions.
Now, our good friend Euler discovered a fascinating relationship between these values.
For any planar graph, n - m + or is equal to 2. Really?
Does that work in this case?
Let's check this formula with the values for this particular graph.
We've got n - m, 5 -6 is -1, plus 3 is indeed 2. Interesting.
We're going to figure out why that is in just a moment,
but let's let you practice first understanding what these regions are.
किनारों और एक planar ग्राफ में नोड्स के बीच संबंधों को समझने की कोशिश करने के लिए
हम एक परिणाम यूलर - से पहले के रूप में एक ही यूलर के कारण का उपयोग करने के लिए जा रहे हैं।
करना है कि हम planar रेखांकन के बारे में एक और अवधारणा की आवश्यकता के लिए जा रहे हैं।
यहाँ पाँच नोड्स पर एक planar ग्राफ है।
फिर से, हम नोड्स के एक धारणा है। हम किनारों की एक धारणा है।
हम भी अब एक planar ग्राफ में क्षेत्र की एक धारणा के बारे में बात करने जा रहे हैं।
क्षेत्रों की तरह है कि ग्राफ में बॉक्स्ड हैं क्षेत्रों रहे हैं,
इसके अलावा इस क्षेत्र ग्राफ के बाहर।
मुड़ता है बाहर है कि एक सच में उपयोगी बात है के बारे में बात करने में सक्षम होना करने के लिए है।
इस विशेष ग्राफ तीन क्षेत्रों है।
हम इसे सही करेंगे 5 नोड्स, 6 किनारों और 3 क्षेत्रों मिल गया है।
अब, हमारे अच्छे दोस्त यूलर इन मानों के बीच एक आकर्षक रिश्ते की खोज की।
किसी भी planar ग्राफ, n - के लिए एम + या 2 करने के लिए बराबर है। वाक़ई?
कि इस मामले में काम करता है?
चलो इस विशेष ग्राफ के लिए मान के साथ इस सूत्र की जाँच करें।
हम n - m, 5 -6 मिल गया है -1, है प्लस 3 2 वास्तव में है। दिलचस्प है।
हम क्यों है कि सिर्फ एक क्षण में बाहर आंकड़ा करने के लिए जा रहे हैं,
लेकिन चलो चलो अभ्यास आपको पहले समझ क्या इन क्षेत्रों रहे हैं।
平面グラフにおける
エッジとノードの関係を理解するには
前と同様にオイラーを利用しましょう
平面グラフに関する別の概念も使います
これはノードが5個の平面グラフです
ノードとエッジがあります
ここで領域の概念について説明します
領域とはグラフの中で区切られた範囲と
グラフの外の範囲のことを指しています
この考えを使うと説明しやすくなります
ここには3つの領域があります
ノードが5、エッジが6、領域が3です
オイラーはこれらの値に
すばらしい関係があることを発見しました
あらゆる平面グラフで
n-m+r=2が成り立つというものです
この例ではどうでしょうか?
公式に値を入れて確かめてみましょう
n-mは5-6なので-1
それに3を足すと確かに2ですね
この理由を考える前に
領域について理解する練習をしましょう