2018-リハーサル-解説
- 考案国：ベルギー
- 正解
- 「Chloe」
- 説明
- バレリーナのデュエットの関係を次のように図で表してみましょう。バレリーナを円で表し、デュエットを踊る2人のバレリーナの円の間を線で結びます。
- バレリーナのどちらかは次のデュエットを踊り、その上、同じバレリーナが３回連続踊ることがないことから、最初の組で踊って次は踊らないバレリーナの円からスタートして、全ての線をちょうど１回ずつ辿れるはずです。（線は2人のバレリーナを結んでいるので、線を辿る順にその線の2人でリハーサルを踊ります。）
- そのためには、最初と最後以外のバレリーナは偶数本の線で結ばれている必要があります。このことから、最初と最後のバレリーナはAかFとなります。AともFともデュエットを組まないバレリーナはCだけです。
- バレリーナのデュエットの関係を次のように図で表してみましょう。バレリーナを円で表し、デュエットを踊る2人のバレリーナの円の間を線で結びます。
- 実際のコンピュータでは
- データの関係を点と線で表す「グラフ」構造で表現することができます。グラフ構造を用いることで、この問題のようにデータ間の関係を視覚化して扱うことが可能になります。
- この問題は、「グラフ」構造で考えると「ある点から出発して全て線をちょうど一度ずつ通ることができるか？」という問題となります。このような線のたどり方を「オイラー路」といいます。
注があるものを除き, このサイトの内容物は
