Japanese 字幕

← 02-23 Complete Graph Solution

埋め込みコードを取得する
3言語

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. この"数式を使うように"というのは
    ちょっとしたトリックです
  2. 完全グラフを生成して
    そのエッジの数を返すコードを書きました
  3. すべてのノードのペアをチェックして
  4. 1個がもう1個より小さければリンクを張ります
  5. こうすれば自身へのリンクや
    反対方向からのリンクは生成されません
  6. よって合計を数え上げることにはなりませんが
    この方が簡潔でしょう
  7. nの値を1から9までについて繰り返して
  8. nの値と
    このクリークのエッジの数を出力してみました
  9. ノードが1、エッジが0のグラフ
  10. ノードが2ならそれをつなぐエッジは1
  11. 3と3は三角形です
  12. 4と6は四角形となりその中でエッジが交わった形です
  13. 5は先ほど見たような5本の線で描く星の形です
  14. こうして増え続けます
  15. n個のノードを持つクリークのエッジの数を
    式に表せるでしょうか?
  16. 各ノードが他のすべてのノードに
    つながる必要があります
  17. そのつながり つまりエッジの数はこのように書けます
  18. この式には注意が必要です
  19. このノードからつなぐ時にこのエッジを数えますが
  20. 反対からつなぐ時にも再び数えるからです
  21. すべてを2回数えるので式はこうなります
  22. つまりΘ(n²)です 再確認しましょう
  23. nの値と
    クリークを作る時に数えたclique(n)を出力すると
  24. n(n-1)を2で割った値と
    完全に一致することが分かります
  25. つまり解答となったこの式は
    この生成処理を考慮しなくても得られるのです
  26. 今まで扱ったグラフは成長率が線形でしたが
    これは2次式となることが分かりました