数学！！「空港に直行便を開設する」例の問題を知っていますか？(´・ω・｀)
(。・ω・)ﾉﾄﾞﾓ
前置き(´⊙ω⊙ˋ)
１週間ぶりくらいの投稿になります
もう2017年も終わりですね～(´・ω・｀)
時間が経つのが早く感じられて非常に焦っています((((;´･ω･`)))
ところで最近おもしろい問題を見かけたので、記事にしてみても良いかな、という事で「空港の問題」を取り上げます(ﾉ °ω° )ﾉ
例によって組み合わせ数学の問題です…はい(´･ω･`)
皆さんの中にも聞いたことがある人はいると思います
では見ていきましょう(((っ･ω･)っ
問題ですお( ＾ω＾)
[問題]
個の空港の間に以下の⑴,⑵,⑶の条件を満たすように直行便を開設するとき、開設の仕方は何通りあるか。
⑴ どの相異なるつの空港
の間にも直行便を開設する。
⑵より
への直行便と、
⑶ ある空港より出発し、直行便を乗り継いで、また
つ存在する。
どうでしょうか(´・ω・｀)
なかなかヤバい雰囲気を醸し出していますね…
この問題は1999年の日本数学オリンピック予選の12問目だそうです
とりあえずこの記事の目的は私自身の記憶の定着でもあるので、何も見ずに解答を書いて行きます
でもその前にちょっとした小話を…(´^p^`)
グラフ理論m9( ﾟДﾟ) ﾄﾞｰﾝ!
この問題は有向グラフというグラフで言い換えることが出来ます
組み合わせの問題で、「ある2人が友達」とか「どこからどこへ行く」といった言葉が出てくる問題では、グラフ理論の道具を使って言い換えると見通しが良くなることがあります
今回の解答ではグラフ理論の言葉は使いませんが、ざっとグラフについて書いておきます(´・ω・｀)
私の備忘録も兼ねております
(読み飛ばしても構いません)
グラフ(∩´∀｀)∩ﾜｰｲ
・グラフ…有限個の頂点と、そのうちの何組かの2頂点を結ぶ辺からなる図形
・次数…ある頂点Pについて、Pを端点とする辺の本数のこと
・彩色グラフ…辺や頂点に色をつけたグラフ
・無向グラフ…辺に向きが無いもの
・有向グラフ…辺に向きを定め、矢印で置き換えたもの
・道(パス)…グラフにおいて、辺をたどって頂点aから頂点bへ行くことが出来るとき、「aからbへの道が存在する」という
・有向道…有向グラフにおいて、向きを加味した道
・半道(セミパス)…有向グラフにおいて、向きを無視した道
・連結…どの2頂点をとっても、その2点がグラフの辺をたどってできる折れ線で結べる状態
・強連結…有向グラフの任意の頂点a,bにおいてaからbへの有向道が存在する状態
・弱連結…有向グラフの任意の頂点a,bにおいてaからbへの半道が存在する状態
・ループ(閉路)…aからaへの道(有向グラフであれば有向道)が存在するとき、それをループという
・有向閉路…有向グラフにおけるループをこのように呼ぶことがある
・DAG(directed acyclic graph)…閉路(有向閉路)のない有向グラフ、有向非巡回グラフとも呼ぶ
・完全グラフ…任意の2頂点間に辺があるグラフ、連結なのは言わずもがな
ここまで説明すれば、上記の問題は「頂点からなる完全有向グラフがループを持つときのグラフの書き方」と言い換えられることが分かると思います
たしかにこれは簡潔に言い表せていますね(´・ω・｀)
初見では解けなかったお(´；ω；｀)
まぁ解けなくて当たり前だと思いますけどね…(´･ω･`)
こんなん解けるわけがない
ちょっとしたヒントを書いておきます(´・ω・｀)↓
が小さい場合で書き出してみて下さい
何か気づくことがあるかも知れません
あとは、余事象を考えると良いです
受験数学では鉄板となっている「少なくとも～というタイプの問題は余事象を考える」というアレが役に立ちます
ちなみに私は余事象では議論が進まないかな〜と、ほぼ考えずに諦めてしまいました(；・∀・)
じゃあそろそろ解説に移ります(((っ･ω･)っ
解説(_´･д･`)_ﾊﾞﾝｯ
問題の⑶の余事象を考えると、グラフは完全なDAG(完全有向グラフで閉路を持たないもの)になります
「完全なDAGには、どの頂点にも矢印をたどって行く事が出来ない頂点がただひとつ存在する」という事実を利用します(´・ω・｀)
この事実から、頂点がただ１通りに「１列化」出来ることを導きます
(こんなん知らなきゃ出来ないです)
まぁ見ていてください(´・ω・｀)
[解答]
個の空港間には直行便が
個あり、そのそれぞれに向きの定め方が
通りあるので、全ての直行便の定め方は
通り…①
ある空港Pからほかの空港への直行便が一つも無いとき、空港Pを「どん詰まりの空港」と呼ぶことにする。
ここで、⑶の余事象を考える。
⑴⑵を満たし、⑶を満たさないように直行便を開設すると、どん詰まりの空港が必ずただひとつ存在することを示す。
(存在性)
どん詰まりの空港が無いと仮定すると、ある空港から一度も行ったことの無い他の空港へ移動することを無限に繰り返すことが出来る。(⑶を満たさないように空港を開設したため)
しかし、空港の数は有限個であるので矛盾。
よってどん詰まりの空港が存在する。
(唯一性)
どん詰まりの空港が2つ以上存在したとすると、どん詰まりの空港a,bが取れるが、そのふたつの間には直行便が開設されていてどん詰まりの空港であることに矛盾。
よってどん詰まりの空港は一つ以下。
以上より、どん詰まりの空港はただひとつ存在することが示された。
ここでどん詰まりの空港をとして、
及び
への直行便を除外する。
すると、同様の議論により、どん詰まりの空港がただひとつ出来る。
これをとし、
及び
への直行便を除外する。
以上の議論を繰り返すことで、空港の列が得られる。
さらに、
から
への直行便が存在する…(*)
となっていることが容易に確認できる。
ある空港の列に対して(*)を満たすように直行便を開設してやると、これは⑴⑵を満たし、⑶を満たさないような直行便の開設の仕方になっていることも容易に確認できる。
(空港から出発すると空港
にしか移動出来ないが、
に戻ってくるためには
を経由しなければならないため)
以上より、⑴⑵を満たし、⑶を満たさないような空港の開設の仕方は通り
したがって、①とあわせて求める場合の数は
通り//
グラフ理論でまとめよう(ΦωΦ)ﾌﾌﾌ…
いかがだったでしょうか(´・ω・｀)
かなり複雑に見えますが、実際はそうでもないです
最後の方は、
⑴⑵を満たし、⑶を満たさない
から
への直行便が存在する
という事を主張しています。
この問題で得られた事実をグラフ理論の言葉を使ってまとめておきましょう(´・ω・｀)
[定理1]
完全なDAGには、ほかの頂点に矢印をたどって移動することが出来ない頂点がただひとつ存在する。
(証明)
主張のような頂点を「どん詰まりの頂点」と呼ぶ。
どん詰まりの頂点が存在しないとすると、ある頂点から矢印をたどって今までに通ったことの無い頂点に移動することを無限に繰り返すことが出来る。しかし、これは頂点が有限個であることに矛盾。(存在性)
どん詰まりの頂点が2つ以上存在したとすると、完全グラフであることから、その二点の間にも辺があり、どん詰まりの頂点であることに矛盾。(唯一性)
以上より、主張は正しい。//
[系]
完全なDAGは、頂点を次の同値な規則
・どん詰まりの頂点P及びPへの矢印を取り除いていく
・[から
への辺が存在する]
によってただ１通りに１列化出来る。
(証明)
主張の後者の規則で頂点を１列化するときのアルゴリズムは主張の前者そのものであるので２つの規則は同値。
主張の規則によって得られる頂点の列は上記の定理により一意に定まる。//
[定理2]
個の頂点からなる完全なDAGの書き方は
通りである。
(証明)
定理1の系より、完全なDAGを与えると頂点の列を返す写像を考えることができる。
ここで、ある頂点の列から、規則
[から
への辺が存在する]
を満たすように完全なDAGを構成すると、ただ１通りのグラフが得られる。
よって、写像//
終わりに(；・∀・)
上の定理の証明は私が頑張って考えたものなので、不備があるかもしれません
申し訳ないです
もし不備を発見した方がいましたらコメントで伝えて下さると助かります
ちなみにこの記事書くのかなーり大変でした！！(´；ω；｀)
より理解が深まると思われる文献を貼っておきます
↓グラフの用語等
http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/06.pdf
↓DAGについて、中盤に１列化の話題あり
http://www.i.kyushu-u.ac.jp/~algo/6.6-7.pdf
不備があったので訂正致しました。申し訳ございません。(2017/12/29 00:01:47)
