前へ / 戻る / 学期末レポートへ $\newcommand{\ol}[1]{\overline{#1}}$ $\newcommand{\card}[1]{\left|\,#1\,\right|}$

今日のまとめ

• グラフの頂点たちを、辺を用いてペアにすることをマッチングと言います。
• できるだけ沢山の頂点がペアになることが嬉しいので「最大マッチング」「完全マッチング」を問題にします。
• 二部グラフと一般のグラフでは「完全マッチング」の意味が違います。
• 二部グラフの「最大マッチング」は、最大フローアルゴリズムを応用したり、ハンガリーアルゴリズムを用いて求められます。
• 一般のグラフの「最大マッチング」を求めるには「増加道」の探索がキーになりますが、易しくはありません。

本講義のまとめ

　この講義では、

• もののつながりを「グラフ」として表現し
• もののつながり方に関する問題を「グラフ問題」として抽象的に読み替え
• 「グラフの定理」や「グラフ・アルゴリズム」で解く

ということを学びました。 見た目が違っても抽象度を上げれば同じもの、ということが世の中にはたくさんあって、 それを見破ることが問題解決の大きな助けになることも少なくありません。 この講義を通じてそういう力が少しでも身に付けてもらえたなら幸いです。
　大変な状況の中、半期の間ご苦労さまでした。あとひとつ、学期末レポートをクリアしてください。

前へ / 戻る / 学期末レポートへ