前回の記事 の続きです。 前回は、最小全域木を求めるアルゴリズムとその「凸っぽさ」を定義し、離散版の凸関数を定義する必要性を述べた。ここからはいよいよその定義に入る。 3.「離散版」凸関数の定義（M凸関数） まず、ユークリッド空間で定義された関数…

☆この記事は、室田一雄・塩浦昭義『離散凸解析と最適化アルゴリズム』の1章及び8～13章をを参考にしていますが、証明の流れや定理の置き方などがかなり大幅に変わっています。誤りがあったらご報告いただけますと幸いです。 はじめに 重み付きグラフの全域木…

最近OMC ( onlinemathcontest.com ) にハマっている。超雑に言うと数学版AtCoderみたいな感じの数学コンテストサイトである。 OMCをやる上で一番の課題は幾何である。ベクトルや三角関数はまだしも、初等幾何は大学に入って以降はおろか大学入試ですらまとも…