2021-いちご-解説

  • 考案国:スイス
  • 正解
    • ビバ子はイチゴのかわりにきのこを置きました。そして、次の図のように枝を抜き取りました。
      2021-CH-04c-正解
  • 説明
    • イチゴが置かれていた「?」には、5本の棒が置かれています。
    • どんぐりや小石を置くと、同じ種類の2箇所とつながっているため、2本の棒をぬき取る必要があります。
    • きのこを置くと、きのことつながっている1本をぬき取るだけですみます。
  • 実際のコンピュータでは
    • ビ太郎が描いた絵は、点と線で関係を表す「グラフ」という構造で考えることができます。
    • グラフの中で、「すべての点が、他の点とつながっている」ような点の集まりをクリークと呼びます。この問題の図では、左と右に、4個ずつの点から作られた四角形のクリークが2個あることがわかります。
    • イチゴを他の物で置き換えると、置かれている物は3種類になりますので、4個の点を使ったクリークは作れなくなるはずです。そこで、4個の点から作られた2個のクリークを壊す棒を探すと、真ん中の縦の棒をぬき取ればよいことがわかります。
    • この問題は、「最小限の色数でグラフを着色する問題」として知られています。そして、スポーツ競技のスケジュール管理、座席表の設計、数独の解答など、多くの用途で利用されています。

powered by Quick Homepage Maker 5.0
based on PukiWiki 1.4.7 License is GPL. QHM

最新の更新 RSS  Valid XHTML 1.0 Transitional