Japanese 字幕

← 01-05 Eulerian Path Solution

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

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

  1. では解説します
  2. このグラフのノードの次数はすべて偶数です
  3. オイラーパスが存在するか試してみましょう
  4. それではEから出発しCへ
  5. 選択肢はいくつかありますがBへ進みます
  6. そこからD、C、A、BそしてEへ
  7. すべてのエッジを1度だけ通ることができたので
  8. オイラーパスがあると言えます
  9. しかしパスには特徴があります
  10. それはEで始まりEで終わっているという点です
  11. パスが同じノードで始まり
    同じノードで終わっているため
  12. Eの次数は偶数となります
  13. なぜなら通過する時はもちろん
  14. 出発し戻ってくる時にもエッジを通るからです
  15. すべてのノードの次数が偶数である
  16. 特殊なオイラーパスをオイラーツアーと呼びます
  17. まるでツアーのように故郷を出発して
  18. 様々なノードを通り故郷に帰ってくるのです
  19. 私たちはグラフのツアーをしたということですね
  20. 以上がオイラーツアーの解説です
  21. 1つ目の解答は不正解です
  22. オイラーパスは存在します
  23. 2つ目の解答も不正解です
  24. このようなグラフには
  25. 必ずオイラーパスが存在します
  26. どのノードから出発したとしても
  27. 必ず出発したノードに戻ってきます
  28. 全ノードの次数が偶数のグラフは
    必ずオイラーパスを持ちますが
  29. オイラーパスを持たないグラフもあります
  30. 分かりやすいように例を紹介します
  31. 3つ以上のノードの次数が
    奇数のグラフを見てみましょう
  32. 4つのノードの次数が奇数のグラフを作ります
  33. 4つのノードF、G、H、Iがあります
  34. すべてのノードの次数を奇数にします
  35. HとGの次数が偶数なので
  36. この2つを結べばすべての次数が奇数になります
  37. これですべてのノードの次数が奇数になりました
  38. どのノードも次数は3です
  39. このグラフのオイラーパスを探してみましょう
  40. Iから始めます
  41. IからG、GからF、FからI、
    IからH、HからF ここで行き止まりです
  42. 他の経路を試します
    HからGへ行ってもまた行き止まりです
  43. 一日中やり続ければ分かると思いますが
  44. 必ず1本のエッジが残ってしまいます
  45. なぜなら全ノードの次数が奇数だからです
  46. 中間のノードは入って出るだけなので
  47. 次数は偶数にしかなり得ないのです
  48. 奇数だと行き詰まってしまいます