数学特別演習（第6回）

今日の授業では、最小全域木 (MST) を構成するプリム (Prim) のアルゴリズムが正しく動くことの証明から行いました。背理法を用いた証明で、理解に若干難しいところもあったかもしれませんが、発表者の人も頑張って説明できたと思います。

授業の後半では、プリムのアルゴリズムのようなものが、一般に greedy algorithm （「欲張り」アルゴリズム）と呼ばれる話や、MST を構成する別の greedy algorithm の例として、クルスカルのアルゴリズムを見ました。

次回は、greedy algorithm が、なぜ、正しく MST を構成できるのか、その辺の舞台裏を探っていくと思います。次回の発表者にも期待したいと思います。