計画数学第二レポート(その1) 提出:e-mail で uno@nii.jp まで。期限は 12/3 (火) 15:00 以下の問題のうち一つを選んで解答しなさい。(()の中が満点) 複数の問題に対して解答した場合は、ボーナス点を ・最小木を求めるクラスカル法のプログラムを作れ。言語は問わない。 プログラムソースと実行例をつけること。(20点) ・最小木を求めるプリム法のプログラムを作れ。言語は問わない。 プログラムソースと実行例をつけること。(20点) ・ グラフ G=(V,E) の任意の2つマッチング M1 と M2 の対称差は交互パス・サイクルのみで構成されることを証明しなさい。(12点) (Gの枝部分集合Mがマッチングである ⇔ M の枝は互いに隣接しない) (交互パス・サイクルマッチングM1 と M2 の交互パス ⇔ M1 と M2 の枝が交互に現れるパス・サイクル) ・ グラフ G=(V,E) の任意のマッチング M に対して、以下の命題を証明しなさい。 M が最大マッチングであれば、またそのときに限り、M に対する増加交互パスがない(12点) (MがGの最大マッチングである ⇔ G は M より要素数の大きいマッチングを含まない) (M に対する増加パス ⇔ M の枝と M 以外の枝が交互に現れるパスで、パスに沿ってMとMでない枝を入れ替えると M よりも要素数の大きなマッチングが得られるもの) ・ ボルトが m1 個、ナットが m2 個あります。みな、同じ大きさに作るつもりだったのですが、やむを得ず、多少形がずれています。あるボルトとナットがはまるかどうかは、そのねじ切りの間隔と直径のずれが 0.2mm以下ならばはまるとしましょう。今、それぞれのボルトとナットのねじ切り間隔・直径はわかっているとします。もっとも多くの、はまる、ボルトとナットの組を見つけるにはどうすればいいでしょうか?(マッチング問題として定式化しなさい)(8点)