Another category of graphs that are very important and come up a lot are planar graphs.
These are graphs that can be drawn in the plane on a flat piece of paper
so that the edges don't cross.
Here's an example of a planar graph.
We've got five nodes and five edges.
You see the way I drew it here. This node here and this node needed to be connected.
I just drew a nice, little curvy line without crossing anything else.
This is a planar graph. It still would be a planar graph even if I drew it with a crossing in it,
because the issue is that there is some way to do it so that the edges don't cross.
Now, in this particular example, we've got five nodes and five edges,
but what we're interested in is what is the relationship in general between the number
of nodes in a planar graph and the number of edges.
This is more complicated example than any of the ones we looked at before in this unit.
There is some kind of a relationship, and there are constraints
by virtue of the fact that the graph is drawn in the plane.
Let's take a look at that. Let's think about adding some edges here.
We can add that edge. We can add this edge. We can add this edge.
We can add this edge, and are there any more edges we can add
while still being able to draw it in a plane? It doesn't look that way, right?
This node is connected to all the other nodes. This one is done.
This node is connected to three other nodes, but it can't reach this one.
It seems like it's sort of all blocked out. That's going to be true in general.
There's going to be some graphs that can't be drawn as a planar graph.
If we add this edge between this node and this node, the resulting graph is no longer planar.
How many edges do we get here all told?
We've got one, two, three, four, five, six, seven, eight, nine.
In this example, the number of edges seems to need to be less than or equal to 9.
कि बहुत ही महत्वपूर्ण हैं और एक बहुत ऊपर आओ ग्राफ की एक अन्य श्रेणी planar रेखांकन कर रहे हैं।
इन रेखांकन कि हवाई जहाज़ में कागज के एक फ्लैट टुकड़ा पर खींचा जा सकता है
इतना है कि किनारों के पार नहीं।
यहाँ एक planar ग्राफ का एक उदाहरण है।
हम पाँच नोड्स और पांच किनारे मिल गया है।
आप जिस तरह से मैं इसे यहाँ आकर्षित किया देखो। यहाँ इस नोड और इस नोड जोड़ा जा करने के लिए की जरूरत है।
मैं बस कुछ और पार करने के बिना एक अच्छा है, थोड़ा वक्रीय लाइन आकर्षित किया।
यह एक planar ग्राफ है। यहां तक कि अगर मैं यह उस में एक पार से आकर्षित किया यह अभी भी एक planar ग्राफ होगा,
क्योंकि समस्या यह है कि कुछ तरह से यह करने के लिए इतना है कि किनारों के पार नहीं है।
अब, इस विशिष्ट उदाहरण में, हम पाँच नोड्स और पांच किनारे मिल गया है,
लेकिन क्या हम में रुचि रखते हैं है क्या रिश्ते के बीच की संख्या सामान्य है
नोड्स का एक planar ग्राफ और किनारों की संख्या में।
यह लोगों में से किसी से भी अधिक जटिल उदाहरण हम पहले इस इकाई में देखा है।
वहाँ किसी तरह का संबंध है, और वहाँ की कमी कर रहे हैं
इस तथ्य के आधार पर कि ग्राफ में हवाई जहाज तैयार है।
चलो उस पर एक नज़र रखना। चलो कुछ किनारों यहाँ जोड़ने के बारे में सोचो।
हम उस किनारे जोड़ सकते हैं। हम इस बढ़त जोड़ें कर सकते हैं। हम इस बढ़त जोड़ें कर सकते हैं।
हम इस बढ़त जोड़ें कर सकते हैं, और वहाँ कोई और अधिक किनारों हम जोड़ सकते हैं कर रहे हैं
अभी भी यह एक हवाई जहाज़ में आकर्षित करने के लिए कर रहा करते समय? यह उस तरह से, सही नहीं दिखता?
इस नोड के लिए सभी अन्य नोड्स से जुड़ा है। यह एक किया जाता है।
इस नोड के लिए तीन अन्य नोड्स से जुड़ा है, लेकिन यह यह एक तक पहुँचने नहीं कर सकता।
ऐसा लगता है जैसे यह की तरह सब ब्लॉक किया गया है। कि सामान्य तौर पर सच होने जा रहा है।
वहाँ जा रहा है कि एक planar ग्राफ के रूप में तैयार किया जा सकता कुछ रेखांकन।
हम इस नोड और इस नोड के बीच इस बढ़त जोड़ते हैं, तो परिणामी ग्राफ़ अब planar है।
कितने किनारों हम यहाँ सब से कहा मिलता है?
हम मिल गया है एक, दो, तीन, चार, पांच, छः, सात, आठ, नौ।
इस उदाहरण में, किनारों की संख्या से कम या बराबर करने के लिए 9 होना चाहिए लगता है।
グラフの種類の中で非常に重要なのが 平面グラフです
エッジが交わらないように 平面上に描けるグラフのことを
平面グラフと呼びます
これは平面グラフの例です
5個のノードと5本のエッジがあります
このノードとこのノードをつなぐために
どこにも交わらない曲線を描いています
もし他のエッジを横切るようにつないだとしても
エッジが交わらないように描くことが可能なグラフは 平面グラフです
この例では5個のノードと5本のエッジがありますが
知りたいのは 平面グラフのノードの数とエッジの数の間に
どのような関係があるかということです
このレッスンで見た中では一番複雑な例ですね
このグラフには ある種の関係性があり
平面上に描けることという制約もあります
それではまずエッジを加えてみましょう
このエッジ、このエッジ、このエッジ、このエッジを 加えます
この平面上で他に追加できるエッジはあるでしょうか? なさそうですね
このノードは他のすべてにつながっています
これは他の3個につながっていますが これとはつなげません
もうこれ以上は追加できないようですね
もしこのノードとこのノードの間に このエッジを加えると平面グラフではなくなります
エッジは全部で何本でしょうか
1、2、3、4、5、6、7、8、9
この例ではエッジの数は9本以下となるようです