点と線で考える

　Ａ，Ｂ，Ｃ，Ｄの４人が，川を渡ろうと岸辺に立っています。この川を渡りたいのですがボートは二人乗りのものが一隻しかありません。しかも，ボートを動かせるのはＡ君だけです。つまり，Ａ君が誰かもう一人を乗せて，川の両岸の間を往復しなければなりません。
　しかし，Ｂ君とＣ君，Ｃ君とＤ君は仲が悪く，Ａ君が一緒にいないとけんかを始めてしまいます。けんかが起きないようにするには，Ａ君はどういう順番で，Ｂ，Ｃ，Ｄの３人を乗せたら良いでしょうか。

　この問題を“点”と“線”を用いて考えてみましょう．
　最初岸にはＡ，Ｂ，Ｃ，Ｄの４人がいて，ＡとＢの２人が川岸へわたったとします．

最初いたのはＡ，Ｂ，Ｃ，Ｄの４人．
残ったのはＣ，Ｄ２人		岸に残った人を考えて，点と線で上のように図示します

　しかし，実際にはＣとＤ人だけが残るとけんかを始めてしまうので，この点と線の組み合わせはよくありません．
　岸に残る人の組み合わせを“点”，点と点を結んで“線”の図を書いていけばよいのです．点は結局{Ａ，Ｂ，Ｃ，Ｄ}の部分集合と考えられ，その個数は２4＝１６個存在することになりますね．これをもとに点と線の図を描いてみましょう．

@A
｛Ａ，Ｂ，Ｃ，Ｄ｝の部分集合を“点”とする図を描きます．(Ａのみは除きます)起こり得る場合を線で結びます
BC
不可能な場合(この場合はＢ君Ｃ君，Ｃ君Ｄ君が２人だけになる場合)を除きます残った場合が答えになります(答えは一通りとは限りません)

　このように点と線だけでできた図形で考えると簡単に解けてしまう問題もあります．この点と線でできた図形を“グラフ”といい，グラフを用いて色々な問題を解いていこうというのが，“グラフ理論”と呼ばれるものです．

《参考資料》