Let's take a look at Euler's formula again.
What we're going to do is prove by induction that this holds.
We can build any planar graph by iteratively adding nodes and edges.
Let's start off with the simplest thing, which is just a single node. Ta-da!
We can start off with just the simplest graph of all--just a node sitting on the plane all by itself,
a lonely point, and we've got one node, no edges, and one giant region around it,
and 1 - 0 + 1 is indeed 2.
That's our base case.
Now we proceed by induction.
Given that we're doing a proof by induction, we're going to assume that we have
some planar graph and that Euler's formula holds for that graph.
We have already that n - m + r = 2.
What we're going to do is we're going to add to this graph so that it's still planar
and see what happens to this formula.
There are two different ways that we can add to this graph.
We can add a node and an edge together, or we can add an edge between two exiting nodes.
Let's consider this first case where we had a new node and an edge between them,
and it's still a planar graph. What happens to m, n, and r?
Well, we have one new node and one new edge but the number of regions hasn't changed.
We're just jutting into some region inside or outside,
but it doesn't change the total number of regions--(n + 1) - (m + 1)--
these ones cancel, and we get n - m + r,
which by our inductive hypothesis we said is 2.
In that case, the formula still holds.
What about the case where we just add an edge.
One way we can add an edge is inside of some other region,
and let's look what happens in that case.
The number of nodes is unchanged. The number of edges has gone up by one.
But the number of regions has gone up by one as well.
This used to be one giant region, and it's now been split in to two regions.
Once again, these ones cancel.
Our formula still holds.
Let's just double-check what happens if we do something on the outside,
sort of breaking into the huge vast region around it.
Connect, say, these two nodes, what have we done?
We still have the vast region around it, but we created a new region here.
Again, the number of regions has gone up by 1.
Similarly, if we click this over the number of regions has gone up by 1.
If we add an edge without a corresponding node, the number of regions goes up by 1.
If we add an edge and a node together, the region stays the same,
but the number of nodes goes up by 1.
No matter what you do, this formula keeps holding. Pretty cool.
चलो फिर से यूलर के सूत्र पर एक नज़र रखना।
क्या हम करने जा रहे हैं कि यह धारण प्रेरण द्वारा प्रमाणित है।
हम iteratively नोड्स और किनारों जोड़ कर किसी भी planar ग्राफ का निर्माण कर सकते हैं।
चलो सरल बात है, जो सिर्फ एक एकल नोड है के साथ शुरू। टा-डा!
हम बस सब - की सबसे आसान ग्राफ के साथ सिर्फ एक नोड से ही सब हवाई जहाज पर बैठा कर सकते हैं बंद शुरू,
एक अकेला बिंदु, और हम एक नोड, कोई किनारों और उसके चारों ओर एक विशाल क्षेत्र मिल गया है,
और 1-0 + 1 2 वास्तव में है।
कि हमारे मूल बात नहीं है।
अब हम प्रेरण द्वारा आगे बढ़ना।
यह देखते हुए कि हम प्रेरण द्वारा एक सबूत कर रहे हैं, हमें लगता है कि हम जा रहे हैं
कुछ planar ग्राफ और उस यूलर के सूत्र के लिए कि ग्राफ आयोजित करता है।
हम पहले से ही है कि एन - एम + r = 2।
क्या हम करने जा रहे है हम इतना है कि यह अभी भी planar है इस ग्राफ को जोड़ने के लिए जा रहे हैं
और देखो क्या इस सूत्र के लिए होता है।
वहाँ दो अलग अलग तरीके है कि हम इस ग्राफ को जोड़ सकते हैं कर रहे हैं।
हम एक नोड और एक छोर एक साथ जोड़ सकते हैं, या हम एक किनारे दो निकल नोड्स के बीच जोड़ सकते हैं।
चलो इस पहले मामले जहां हम एक नए नोड और उन दोनों के बीच एक छोर था पर विचार,
और यह अभी भी एक planar ग्राफ है। क्या एम, एन, और r के लिए होता है?
ठीक है, हम एक नए नोड और एक नई धार है लेकिन क्षेत्रों की संख्या नहीं बदला है।
हम बस कुछ क्षेत्र के अंदर या बाहर jutting हो,
लेकिन यह क्षेत्र-(n + 1) - की कुल संख्या परिवर्तित नहीं करता (m + 1) -
इन लोगों को रद्द करें, और हम n - m + r हो,
जो हमारा आगमनात्मक अनुमान से कहा कि हम 2 है।
उस मामले में, सूत्र अभी भी आयोजित करता है।
क्या मामला है जहाँ हम अभी बढ़त जोड़ने के बारे में।
एक तरह से हम एक एज जोड़ सकते हैं कुछ अन्य क्षेत्र के अंदर है,
और आइए देखें क्या उस स्थिति में होता है।
नोड्स की संख्या अपरिवर्तित है। किनारों की संख्या एक से बढ़ गई है।
लेकिन क्षेत्रों की संख्या में से एक ने भी चला गया।
यह एक विशाल क्षेत्र हुआ करता था, और यह अब में दो क्षेत्रों को विभाजित किया गया है।
एक बार फिर से, इन लोगों को रद्द करें।
हमारे फार्मूला अभी भी आयोजित करता है।
चलो बस दोहरी जांच अगर हम बाहर कुछ करना क्या होता है,
की तरह विशाल विशाल क्षेत्र के आसपास यह तोड़।
, कहते हैं, इन दो नोड्स, क्या है कनेक्ट किया हम?
हम अभी भी यह चारों ओर विशाल क्षेत्र है, लेकिन हम एक नए क्षेत्र यहाँ बनाया है।
फिर से, क्षेत्रों की संख्या 1 से बढ़ा है।
अगर हम इस पर क्लिक करें इसी प्रकार, क्षेत्रों की संख्या 1 से बढ़ा है।
यदि हम एक संगत नोड के बिना बढ़त जोड़ने, क्षेत्रों की संख्या 1 से ऊपर जाता है।
हम एक एज और एक नोड एक साथ जोड़ते हैं, तो इस क्षेत्र एक ही रहता है,
लेकिन नोड्स की संख्या 1 से ऊपर चला जाता है।
कोई बात नहीं क्या आप करते हैं, इस सूत्र पकड़ रखता है। बहुत अच्छा।
再びオイラーの公式を見ましょう
これが成り立つかを帰納法で証明してみます
どんな平面グラフも
ノードとエッジの追加を繰り返すことで描けます
それではノードが1個という単純な例から始めましょう
最も単純なのはノードが1個だけあるというグラフです
ノードが1個あってエッジはなく
周りに巨大な領域があります
1-0+1で2になりますね
これがベースケースです
帰納法で考えてみましょう
ある平面グラフがあって
それにオイラーの公式が当てはまると仮定します
すでにn-m+r=2という式が与えられています
ここにノードやエッジを追加した時に
公式がどうなるかを確かめましょう
方法は2種類あります
ノードとエッジを同時に加えるか
既存のノードの間にエッジを加えます
1のケースを試しましょう
新しいノードとエッジを加えます
これも平面グラフです n、m、rの値は?
ノードが1、エッジが1増えると
領域の数は変わりません
この領域の中に突き出していますが
領域の総数は変わらないので
(n+1)-(m+1)+rです
この1は消えてn-m+rとなります
帰納法の仮定で2でしたね
このケースでは公式は成り立ちます
エッジだけを加えるケースは?
まず領域の中にエッジを加えるケースを考えましょう
ノードの数は変わらずエッジの数は1増えます
領域の数も1増えますね
この領域は2つに分割されました
またこの1は消えるので公式は成り立ちます
外側の大きな領域に変化を加えた時に
どうなるかを再確認してみましょう
例えばこの2個をつなぐと
ここに新しい領域ができました
領域の数は1増えました
同様にここをつなぐと領域の数は1増えます
エッジだけを加えると領域の数は1増えます
エッジとノードを同時に加えると
領域の数は変わりません
ノードとエッジの数はそれぞれ1増えます
何をしても公式が成り立ちます すごいですよね