I told you to use a mathematical formula, so I cheated a little bit.
I wrote a little piece of code to actually generate a complete graph
and then return the number of edges in that graph.
To make a complete graph, I just looped through all the pairs of nodes,
and if one node was smaller than the other, then I made a link between them.
That was mainly to just make sure I didn't make a link from nodes to themselves.
There is no reason not to make a link the other way.
It would have not counted against the total, but this seemed nicer and cleaner.
Let's look at what happens if you loop on all the different values of n
from 1 to 9 and print n and the number of edges in the clique.
A graph with one node has no edges.
A graph with 2 nodes fully connected has one edge, 3 has three--that's a triangle,
4 has six, which is the square with the x through the middle of it,
5 is that pentagram-looking thing that we just showed a minute ago,
and it continues growing up like that.
With that as our insight, can we actually write down what the formula is
for a graph with n nodes?
Essentially what happens is each node gets an edge to each other node,
which we can write as each node has an edge to each other node.
Notice what happens if we use that as our formula, we're going to count this edge,
as it goes from this node to this node.
We're also going to count it again, as it goes from this node to this node.
We've double counted everything, so that should be our formula,
which is Î(nÂ˛). Let's just double-check this.
If we print n, clique (n), which I counted by actually creating the clique,
compared that to the formula n * (n -1)/2,
you can see that it matches up perfectly.
So, really the answer that you should have given is this--
shouldn't have bothered with any of this creating of stuff.
Now, in addition to all those graphs where the growth rate was linear, we now have one that's quadratic.
मैं तुम्हें एक गणितीय सूत्र का उपयोग करें तो मैं थोड़ा धोखा दिया करने के लिए कहा था।
मैं वास्तव में एक पूर्ण ग्राफ उत्पन्न करने के लिए कोड का एक छोटा सा टुकड़ा लिखा था
और फिर किनारों की संख्या कि ग्राफ में वापस जाएँ।
एक पूरा ग्राफ़ बनाने के लिए, मैं सिर्फ नोड्स के सभी पेयर्स के माध्यम से looped,
और फिर अगर एक नोड दूसरे से छोटा था, मैं उन दोनों के बीच एक लिंक बना दिया।
कि मुख्य रूप से सिर्फ यकीन है कि मैं खुद के लिए नोड्स से एक लिंक बना था करने के लिए गया था।
वहाँ एक लिंक अन्य रास्ता नहीं करने के लिए कोई कारण नहीं है।
यह कुल के खिलाफ नहीं गिना है होता है, लेकिन इस अच्छे और क्लीनर लग रहा था।
चलो अगर आप सभी विभिन्न मूल्यों के n पर पाश क्या होता है देखो
1 से 9 और प्रिंट एन और गुट में किनारों की संख्या के लिए।
एक ग्राफ एक नोड के साथ कोई किनारों है।
2 नोड पूरी तरह से जुड़ा के साथ एक ग्राफ एक एज, 3 तीन - एक त्रिकोण है कि है,
4 छह, जो वर्ग के मध्य यह के माध्यम से एक्स के साथ है है,
5 कि पेंटाग्राम लग रही बात है कि हम सिर्फ एक मिनट पहले से पता चला है,
और यह रहा है कि जैसे आगे बढ़ रही है।
के साथ कि हमारी अंतर्दृष्टि के रूप में, हम वास्तव में क्या फार्मूला है नीचे लिख सकता है
n नोड्स के साथ एक ग्राफ के लिए?
अनिवार्य रूप से क्या होता है प्रत्येक नोड नोड एक दूसरे के लिए एक किनारे हो जाता है,
जो हम लिख सकता है के रूप में प्रत्येक नोड एक छोर एक दूसरे नोड के लिए है।
सूचना क्या होता है अगर हम का उपयोग करें कि हमारे सूत्र के रूप में, हम इस किनारा गिनने के लिए जा रहे हैं,
के रूप में यह करने के लिए इस नोड इस नोड से चला जाता है।
यह करने के लिए इस नोड इस नोड से चला जाता है के रूप में हम भी इसे फिर से, गणना करने के लिए जा रहे हैं।
इसलिए कि हमारे सूत्र होना चाहिए सब कुछ, डबल गिना है,
जो मैं (nÂ˛) है। चलो बस यह दोहरी जांच।
अगर हम n मुद्रित, गुट (एन), जो मैं वास्तव में से गिना गुट बनाने,
सूत्र n करने के लिए तुलना में * (n -1) / 2,
आप देख सकते हैं कि यह पूरी तरह से मैच।
तो, वास्तव में जवाब है कि आप दिया जाना चाहिए यह है-
किसी भी इस के सामान बनाने के साथ परेशान नहीं करना चाहिए।
अब, सभी उन रेखांकन के अलावा जहां विकास की दर रैखिक था, अब हम एक है कि द्विघात है है।
この"数式を使うように"というのは ちょっとしたトリックです
完全グラフを生成して そのエッジの数を返すコードを書きました
すべてのノードのペアをチェックして
1個がもう1個より小さければリンクを張ります
こうすれば自身へのリンクや 反対方向からのリンクは生成されません
よって合計を数え上げることにはなりませんが この方が簡潔でしょう
nの値を1から9までについて繰り返して
nの値と このクリークのエッジの数を出力してみました
ノードが1、エッジが0のグラフ
ノードが2ならそれをつなぐエッジは1
3と3は三角形です
4と6は四角形となりその中でエッジが交わった形です
5は先ほど見たような5本の線で描く星の形です
こうして増え続けます
n個のノードを持つクリークのエッジの数を 式に表せるでしょうか?
各ノードが他のすべてのノードに つながる必要があります
そのつながり つまりエッジの数はこのように書けます
この式には注意が必要です
このノードからつなぐ時にこのエッジを数えますが
反対からつなぐ時にも再び数えるからです
すべてを2回数えるので式はこうなります
つまりΘ(n²)です 再確認しましょう
nの値と クリークを作る時に数えたclique(n)を出力すると
n(n-1)を2で割った値と 完全に一致することが分かります
つまり解答となったこの式は この生成処理を考慮しなくても得られるのです
今まで扱ったグラフは成長率が線形でしたが これは2次式となることが分かりました