教えてください

質問

次の問題がわかりません・・・。
皆さん教えてください↓
第一問 一辺が１の立方体ABCD-EFGHを、対角線AGを含む平面で切断するとき、
切り口の面積の最小値を求めよ。

第二問　ｎ個の空港の間に以下の(・),(・)の条件を満たすような直行便を開設するとする。
（ｎ≧３とする）
(・) どの相違なる二つの空港A,Bの間にも、AからBへの、あるいはBからAへの直行便のどちらか一方を開設する。
(・) ある空港Cから出発し、直行便を乗り継いで、またCに戻ってこられるような空港Cが少なくとも1つは存在する。
このように開設する方法がaｎ通りあるとする。
(1)a3を求めよ
(2)a4を求めよ
(3)anを求めよ
よろしくお願いします。

回答No.3

stomachman

第二問ですけど、Umadaさんと答は一致しました。しかしアプローチはいささか違うと思うので、ご参考までに。

　空港を頂点とし、直行便を辺とするグラフ（辺が向きを持つ有向グラフ）を作ると考えます。n個の空港のどの2つを取っても直行便があるんですから、もし辺の向きを無視すれば、これはただ一つ「完全グラフ」（どの頂点の間にも辺がある無向グラフ）しかありえません。すると問題は「少なくとも一つループができるように、完全グラフの辺に向きを付ける方法は何通りあるか」と言い換えられます。完全グラフの各辺に向きを与える方法は、辺の数をEとすると2^E通りあり、そしてE=n(n-1)/2ですね。だから「ループがないように辺に向きを付ける方法が何通りあるか」が分かれば、その数を2^Eから差し引けば良い。

　ループがないって事は、頂点間に順序が定義できるということに他なりません。「頂点xからyへの経路がある」という事をx<yと表したとき、どの頂点間でも直行便があるので、<は全順序になっていなくてはならない。
きちんと言えば、空港の集合をAとするとき、関係<が存在して
∀i∈A(￢(i<i))
∀i,j∈A( i≠j → i<j ∨ j< i)　（全順序である）
∀i,j∈A( i<j → ￢(j< i))　　　（ループがない）
∀i,j,k∈A( i<j∧j<k → i< k)　（推移則）
を満たす、ということですが （￢はnot、つまり否定を表す論理演算子です）ま、細かいことは重要じゃない。

ループがないのなら、この全順序<を使って頂点を一列に並べることができます。
a[1]<a[2]<.....<a[n]
また、このような列が一つ与えられると、「p<q なら pからqへの直行便がある」と解釈すれば有向グラフが丁度一つ作れます。かくて、このような列の数だけ「ループができないように辺に向きを付ける方法」がある訳です。もちろん、その数は頂点を一列に並べる順列の個数と等しく、すなわちn!通りあります。

以上から、「少なくとも一つループができるように辺に向きを付ける方法」は
2^(n(n-1)/2) - n!
通りあるということです。
n=3 では 2通り、 n=4では40通り。