YouTube

Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

Japanese subtitles

← 02ps-02 Subsets Solution

Get Embed Code
3 Languages

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

  1. 部分集合の問題の最初では
    平面グラフとツリーグラフについて考えます
  2. すべての平面グラフがツリーグラフとは限りません
  3. このリングは平面グラフですが
    ツリーグラフではありません
  4. 平面グラフはツリーグラフの部分集合ではありませんが
    反対にツリーグラフはすべて平面グラフです
  5. ほとんどのツリーグラフは直感的に平面グラフで表せます
  6. 例えばこのようなグラフです
  7. しかしツリーでも平面にするのは難しい場合もあります
  8. そこですべてのツリーは平面であると証明されていると
  9. 直感だけに頼らずに済みます
  10. 証明方法の1つとしてツリーグラフを三角形で表し
  11. より大きいツリーの場合
    三角形を組み合わせて構造化します
  12. 正式にはツリーは任意のノードを頂点とする
  13. 三角形の平面で表すことができます
  14. ノードが1個なら頂点にはそのノードがきます
  15. これはとても簡潔な表現です
  16. 帰納法的に考えるとnより小さいノードで
    真であることが証明されれば
  17. nのノードのすべてのグラフでも真であると言えます
  18. このグラフを例にとってみましょう
  19. ランダムに選んだ1個のノードをrとします
  20. 例えばこれをrとし 次にrを取り除きます
  21. 最初のグラフがツリーだったので
    次も別々のツリーになります
  22. これらのツリーはそれぞれノードがnより小さいので
  23. それぞれを三角形で表します
  24. まずこのノードが4個のツリーを三角形で表します
  25. 頂点になるノードはrに連結していたものになります
  26. 他の2つのツリーについても同様にします
  27. そして最後にrを頂点とした大きな三角形を作り
  28. 3つの三角形の頂点とrを連結させます
  29. これによりすべてのツリーグラフは
    平面グラフであると証明されます
  30. ツリーの定義によりツリーとリングは
    同時成立しません
  31. ツリーはサイクルでなくてもいいが
    リングはサイクルでなければいけない
  32. 答えはどちらも偽ですね
  33. チェーンについては例では説明がつきますが
    明確な定義が分かりません
  34. チェーンの場合もリングと違いサイクルがありません
  35. もうひとつ明確なのはチェーンのエッジは
    ノードがnの場合n-1であることです
  36. リングのエッジはノードの数と同じです
  37. だから両者はお互い排他的で違うものです
  38. チェーンはツリーに含まれますが
    ツリーは必ずしもチェーンではありません
  39. これによりツリーは連結しているがサイクルがなく
  40. 1組のノードにはエッジが1本だと定義できます
  41. チェーンにも同じことが言えます
  42. これは例を書いてみると直感的に分かることです
  43. この定義には100%自信があります
  44. 簡単な例を挙げてみると
    これはツリーであるがチェーンではないというわけです
  45. 次にリングではないハイパーキューブまたは
  46. ハイパーキューブではないリングを考えてみました
  47. 4個のノードを持つリングを除き
    すべてのリングはハイパーキューブにはなりません
  48. また4個のノードのハイパーキューブを除く
    すべてのハイパーキューブはリングではありません
  49. 例を書いてみましょう これは普通の立方体です
  50. 最後から2番目の問題は格子とチェーンです
  51. すべてのチェーンは格子ですが
    格子はすべてチェーンではありません
  52. ノードがnのチェーンを格子で表すと1×nです
  53. 格子のどちらか一方に
    もう1つ格子ができればチェーンではなくなります
  54. どんなに長くチェーンを作っても
  55. チェーンにn個のノードを加えると
    格子ではなくなります
  56. あなたが最初に言ったように
    1×nの格子はチェーンですが
  57. これはチェーンではないということですね