2021-森の見はり-解説
- 考案国：オーストリア
- 正解
- 3つの見はり台を使った下の図が正解です。
- 3つの見はり台を使った下の図が正解です。
- 説明
- 道は8本あります。
- もし見はりだいを2つしか使わないと、4本ずつ見はる必要がありますが、4本の道を見はることのできる見はりだいはありませんので、2つの見はりだいではぜんぶの道を見はれないことがわかります。
- 実際のコンピュータでは
- コンピュータの世界では、多くの情報を、点と線で表す「グラフ」で扱います。この問題では、グラフは次の図のように表せます。
- この問題は、「すべての線が、選ばれた点のどれかにつながっている」と考えることができます。このような問題は最小頂点被覆問題と呼ばれ、「すべての通りを照らすことのできる街灯の配置」や「すべての廊下を撮影できるカメラの配置」などを考えるときに使うことができます。
- コンピュータの世界では、多くの情報を、点と線で表す「グラフ」で扱います。この問題では、グラフは次の図のように表せます。
注があるものを除き, このサイトの内容物は
