The first part of the subset question asks about planar graphs and trees.
The first thing to note is that not all planar graphs are trees.
For example, here's a ring, which is a planar graph and it's not a tree.
And so planar graphs are not a subset of trees. On the other hand, all trees are planar graphs.
For most trees, it's fairly intuitive to see how it can be drawn in the plane.
For example, this one is already planar.
But for other trees, it might not be so obvious that we can rearrange everything
to lay it outside in the plane, and so it'd be nice to have a proof that all trees are planar
instead of relying just on intuition.
One way to prove this is to show that any tree can be drawn inside of a triangle.
And then larger trees can be constructed by combining these triangles.
More formally, what we want to show is that any tree can be drawn in a plane inside a triangle
with any given node at the apex of the triangle.
And so for the base case of one node, we can draw the node at the apex of the triangle
and this is trivially in a plane.
And so, our inductive step is to assume that the claim is true for all graphs with less than n nodes.
And we want to show that the claim is true for all graphs with n nodes.
So we'll start with a tree with n nodes. We use this for example.
We're going to pick any node kind of at random and we'll call it r.
For example, one of this node be r. And then we remove r.
Because our original graph was a tree, this separates the graph into separate disjoint trees.
And now since each of these trees have less than n nodes,
we can draw each one inside of a triangle.
First, we can take this tree of four nodes and draw it inside of the triangle.
Notice that the node that was connected to r is at the apex of the triangle.
And then we could do the same for the other two trees.
And then in our last step, we'll make a bigger triangle and we put r at the apex
and then connect it to the apexes of the other triangles.
This verifies our claim and shows that all tree graphs are planar.
They are definitely neither due to the definition of trees.
A tree can have no cycles and a ring must have a cycle.
The answer is neither. >>Yeah. >>Cool.
I never got a really specific definition of a chain besides just the example which was enough but--
Yeah, same idea kind of a chain doesn't have a cycle whereas a ring does.
And the other thing we got definitely was that the edges in the chain is the number of nodes minus 1
and the edges in the ring is equal to the nodes.
Therefore, there can be no crossover between them. They're mutually exclusive.
All chains are trees but not all trees are chains and so its the first one.
It satisfies the definition of a tree graph that it's connected but there are no cycles,
and then the other description of a tree graph that every pair of nodes in the graphs
has a unique path between them.
I mean a chain does that also.
This is definitely one that answer intuitively by looking at the examples.
It gives me 100% confidence in making that claim.
Yeah and just kind of a quick example of--that's a tree and that is not a chain so--
Correct. And the way I convinced myself of that is drawing an example of a hypercube
that was not a ring and a ring that was not a hypercube.
Unless you have a ring that is anything but four nodes it's not a hypercube.
Okay. >>And any hypercube that's anything but four nodes is definitely not a ring.
Great. So yeah I'll draw one for you and it's just a normal cube.
Right. >>And our second to the last problem is just grids and chains.
All chains are grids but not all grids are chains so it's the--chains are the opposite of grids.
Yeah. >>Any chain within nodes is a 1xn grid.
Once you get a grid that has more than one in either of the two directions, it's no longer a chain.
And no matter how long you make a chain-- >>Yeah. So this is--
You can add a node to the chain--a node of n to the chain, that makes it not a grid.
Kind of the first thing you said we have like a 1xn grid and it's also a chain but yeah.
Yeah. This is for example not a chain. >>Correct. >>Cool.
सबसेट सवाल का पहला हिस्सा planar रेखांकन और पेड़ों के बारे में पूछते हैं।
नोट के लिए पहली बात यह है कि नहीं सभी planar रेखांकन पेड़ हैं।
उदाहरण के लिए, यहाँ है एक अंगूठी जो एक planar ग्राफ है, और यह एक पेड़ नहीं है।
और पेड़ों की एक सबसेट तो planar रेखांकन नहीं रहे हैं। दूसरी ओर, सभी पेड़ planar रेखांकन कर रहे हैं।
अधिकांश पेड़ों के लिए, यह काफी कैसे यह हवाई जहाज़ में तैयार हो कर सकते हैं देखने के लिए सहज ज्ञान युक्त है।
उदाहरण के लिए, यह एक पहले से ही planar है।
लेकिन अन्य वृक्षों के लिए, यह इसलिए कि हम सब कुछ को पुनर्व्यवस्थित कर सकते हैं स्पष्ट नहीं हो सकता है
यह बाहर विमान में, लेआउट के लिए और यह एक सबूत है कि सभी पेड़ planar है अच्छा होगा तो
बस अंतर्ज्ञान पर भरोसा करने के बजाय।
एक तरह से यह साबित करने के लिए कि किसी भी पेड़ एक त्रिकोण के अंदर तैयार हो कर सकते हैं दिखाने के लिए है।
और फिर बड़ा पेड़ इन त्रिकोण के संयोजन से खड़े हो सकते हैं।
और अधिक औपचारिक रूप से, क्या हम दिखाना चाहते हैं कि किसी भी पेड़ एक त्रिकोण के अंदर एक हवाई जहाज़ में खींचा जा सकता है
त्रिकोण के शीर्ष पर किसी भी दिए गए नोड के साथ।
और तो एक नोड के आधार मामले के लिए, हम नोड त्रिकोण के शीर्ष पर आकर्षित कर सकते हैं
और यह trivially में एक हवाई जहाज़ है।
और तो, हमारे आगमनात्मक कदम लगता है कि दावा कम से कम n नोड्स के साथ सभी रेखांकन के लिए सच है।
और हमें पता चलता है कि दावा सच n नोड्स के साथ सभी रेखांकन के लिए करना चाहते हैं।
तो हम n नोड्स के साथ एक पेड़ के साथ शुरू करेंगे। हम इस उदाहरण के लिए का उपयोग करें।
हम किसी भी नोड पर की तरह यादृच्छिक लेने के लिए जा रहे हैं और हम इसे आर फोन करता हूँ।
उदाहरण के लिए, इस नोड में से एक आर हो। और फिर हम आर निकालें।
क्योंकि हमारे मूल ग्राफ़ एक पेड़ था, यह अलग-अलग विसंधित पेड़ों में ग्राफ अलग करता है।
और अब इन पेड़ों में से प्रत्येक के बाद से n नोड्स की तुलना में कम है,
हम में से हर एक एक त्रिकोण के अंदर आकर्षित कर सकते हैं।
सबसे पहले, हम चार नोड्स के इस पेड़ ले और यह त्रिकोण के अंदर आकर्षित कर सकते हैं।
सूचना है कि नोड के लिए आर से जुड़ा था त्रिभुज का शीर्ष पर है।
और फिर हम अन्य दो पेड़ों के लिए एक ही कर सकता है।
और फिर हमारे पिछले चरण में, हम एक बड़ा त्रिभुज बनाती हूँ और हम पर सर्वोच्च आर डाल
और तब यह अन्य त्रिकोण के apexes करने के लिए कनेक्ट।
यह हमारे दावे की पुष्टि और पता चलता है कि सभी पेड़ ग्राफ़ planar हैं।
वे निश्चित रूप से पेड़ों की परिभाषा के कारण न तो कर रहे हैं।
एक ट्री कोई चक्र है सकते हैं और एक अंगूठी एक चक्र होना चाहिए।
इसका जवाब न तो है। >> हाँ। >> शांत।
मैं कभी नहीं मिला है जो पर्याप्त है लेकिन - था सिर्फ उदाहरण के अलावा एक श्रृंखला के एक सच में विशिष्ट परिभाषा
एक अंगूठी है हाँ, एक ही विचार की तरह एक श्रृंखला एक चक्र है, जबकि नहीं करता।
और दूसरी चीज़ हमें मिल गया था निश्चित रूप से है कि श्रृंखला में किनारों है शून्य से 1 नोड्स की संख्या
और किनारों के रिंग में नोड्स के लिए बराबर है।
इसलिए, हो सकता कोई अंतरराष्ट्रीय उन दोनों के बीच। वे परस्पर अनन्य हैं।
सभी जंजीरों के पेड़ हैं, लेकिन नहीं सभी पेड़ हैं और तो यह पहले से एक है।
यह एक पेड़ ग्राफ कि यह कनेक्टेड है की परिभाषा संतुष्ट करता, लेकिन वहाँ कोई चक्र हैं,
और फिर एक पेड़ का अन्य विवरण ग्राफ कि रेखांकन में नोड्स के प्रत्येक जोड़ी
उन दोनों के बीच एक अद्वितीय पथ है।
मेरा मतलब है कि एक श्रृंखला भी है।
यह निश्चित रूप से एक है कि intuitively का जवाब उदाहरणों को देखना है।
यह 100% विश्वास का दावा है कि बनाने देता है।
हाँ और बस एक त्वरित उदाहरण के - की तरह है कि एक पेड़ और कि एक श्रृंखला तो नहीं है-
सही है। और जिस तरह से मैं यकीन है कि अपने आप को एक उदाहरण के एक hypercube का आ रहा है
कि एक अँगूठी और एक अंगूठी जो एक hypercube नहीं था नहीं था।
जब तक आप एक अंगूठी है कि लेकिन कुछ चार नोड्स है यह एक hypercube नहीं है।
ठीक. >> और किसी भी hypercube लेकिन कुछ चार नोड्स है कि निश्चित रूप से एक की अंगूठी नहीं है।
शानदार. हाँ तो मैं आप के लिए एक आकर्षित करेंगे और यह सिर्फ एक सामान्य घन है।
सही है। >> और पिछले समस्या करने के लिए हमारी दूसरी बस ग्रिड और चेन है।
सभी जंजीरों ग्रिड हैं, लेकिन नहीं सभी ग्रिड चेन हैं तो यह है-चेन ग्रिड के विपरीत कर रहे हैं।
हाँ. >> एक 1xn ग्रिड नोड्स के भीतर किसी भी श्रृंखला है।
एक बार जब आप किसी ग्रिड या तो दो दिशाओं में एक से अधिक है, यह अब एक श्रृंखला है।
और कोई बात नहीं कितना समय आप एक श्रृंखला - कर >> हाँ। तो यह है-
आप चेन - चेन, कि यह नहीं एक ग्रिड के लिए n का एक नोड के लिए एक नोड जोड़ें कर सकते हैं।
पहली बात आप ने कहा कि हम एक 1xn ग्रिड और यह की तरह है की तरह भी लेकिन हाँ एक श्रृंखला है।
हाँ. इस उदाहरण के लिए एक श्रृंखला नहीं है। >> सही। >> शांत।
部分集合の問題の最初では 平面グラフとツリーグラフについて考えます
すべての平面グラフがツリーグラフとは限りません
このリングは平面グラフですが ツリーグラフではありません
平面グラフはツリーグラフの部分集合ではありませんが 反対にツリーグラフはすべて平面グラフです
ほとんどのツリーグラフは直感的に平面グラフで表せます
例えばこのようなグラフです
しかしツリーでも平面にするのは難しい場合もあります
そこですべてのツリーは平面であると証明されていると
直感だけに頼らずに済みます
証明方法の1つとしてツリーグラフを三角形で表し
より大きいツリーの場合 三角形を組み合わせて構造化します
正式にはツリーは任意のノードを頂点とする
三角形の平面で表すことができます
ノードが1個なら頂点にはそのノードがきます
これはとても簡潔な表現です
帰納法的に考えるとnより小さいノードで 真であることが証明されれば
nのノードのすべてのグラフでも真であると言えます
このグラフを例にとってみましょう
ランダムに選んだ1個のノードをrとします
例えばこれをrとし 次にrを取り除きます
最初のグラフがツリーだったので 次も別々のツリーになります
これらのツリーはそれぞれノードがnより小さいので
それぞれを三角形で表します
まずこのノードが4個のツリーを三角形で表します
頂点になるノードはrに連結していたものになります
他の2つのツリーについても同様にします
そして最後にrを頂点とした大きな三角形を作り
3つの三角形の頂点とrを連結させます
これによりすべてのツリーグラフは 平面グラフであると証明されます
ツリーの定義によりツリーとリングは 同時成立しません
ツリーはサイクルでなくてもいいが リングはサイクルでなければいけない
答えはどちらも偽ですね
チェーンについては例では説明がつきますが 明確な定義が分かりません
チェーンの場合もリングと違いサイクルがありません
もうひとつ明確なのはチェーンのエッジは ノードがnの場合n-1であることです
リングのエッジはノードの数と同じです
だから両者はお互い排他的で違うものです
チェーンはツリーに含まれますが ツリーは必ずしもチェーンではありません
これによりツリーは連結しているがサイクルがなく
1組のノードにはエッジが1本だと定義できます
チェーンにも同じことが言えます
これは例を書いてみると直感的に分かることです
この定義には100%自信があります
簡単な例を挙げてみると これはツリーであるがチェーンではないというわけです
次にリングではないハイパーキューブまたは
ハイパーキューブではないリングを考えてみました
4個のノードを持つリングを除き すべてのリングはハイパーキューブにはなりません
また4個のノードのハイパーキューブを除く すべてのハイパーキューブはリングではありません
例を書いてみましょう これは普通の立方体です
最後から2番目の問題は格子とチェーンです
すべてのチェーンは格子ですが 格子はすべてチェーンではありません
ノードがnのチェーンを格子で表すと1×nです
格子のどちらか一方に もう1つ格子ができればチェーンではなくなります
どんなに長くチェーンを作っても
チェーンにn個のノードを加えると 格子ではなくなります
あなたが最初に言ったように 1×nの格子はチェーンですが
これはチェーンではないということですね