1. はじめに 今回は，奇数サイズの部分集合の中で，劣モジュラ関数値が最小なものを求める方法を紹介します．劣モジュラ関数が多項式時間で最小化できることは広く知られていますが，実は劣モジュラ関数を最小化する奇数サイズ集合も，通常の劣モジュラ最小…
今回は，マトロイドの最大重み基を求める貪欲法でないアルゴリズムを紹介します*1． マトロイドの最大重み基は，重みの大きな要素から選んでいく貪欲法によって求められます．この事実は多分有名だと思いますが，ではそれ以外の方法でマトロイドの最大重み基…
久々の更新ですが，今回は今まで読んだ数学の本を紹介します*1*2．離散数学や組合せ最適化の本がメインです． グラフ理論 （R. Diestel） グラフ理論 (Springer‐Verlag GTMシリーズ) 作者:R. ディーステル メディア: 単行本 グラフ理論について広く浅く書か…
線形計画問題が楕円体法などによって多項式時間で解けることは有名です．しかし，例えばある問題のLP表現において，制約式の個数がその問題の入力長に関して指数個あった場合，その問題は普通の楕円体法では多項式時間で解くことはできません．では，そのよ…
院試勉強にもそろそろ飽きてきたので、気分転換に数理情報学専攻の専門数学の予想問題を作ってみました。計数工学科内では有名な（？）話題に関する問題ですが、ちょっとマニアックなので、暇な人は解いてみてください。難易度は難しめ（&分量多め）だと思い…
今回は、すべての頂点の次数が3以上のグラフは$K_4$をマイナーとして含むという話を紹介しようと思います。一見簡単そうな主張ですが、厳密に証明するのは意外と大変です。 1. 主張の内容 以下の主張が成り立ちます。 $G=(V, E)$を無向単純グラフ*1とする。…
最近輪講で"Compact Data Structures(Gonzalo Navarro, 2016)"という本を読んでいるのですが、そこでCardinal Treeと呼ばれる木の個数がn頂点のとき$$\frac{\binom{nk+1}{n}}{nk+1}$$個（$k$は子の最大個数）であると紹介されていました。その証明を考えてみ…
今回は、グラフ理論分野における超有名定理、最大流最小カット定理の証明について書いてみようと思います。 最大流最小カット定理は証明方法がいくつかありますが、今回は線形計画法の双対を用いた証明を紹介します。この証明方法はFord-Fulkersonのアルゴリ…
どんな平面グラフも4彩色*1可能という事実は、四色定理という名で広く知られています。では、4彩色を少し拡張した概念である、4リスト彩色については任意の平面グラフに対して可能なのか？というのが今回の話です。 まず、リスト彩色とは以下のように定義さ…
今回は木幅（tree-width）の話を書いてみようと思います。 木幅とは、大雑把に言うとグラフがどれだけ木に近いかを表す値です（木に近いほど小さな値になります）。NP困難な問題でもグラフを木に限定すると多項式時間で解けたりする話は有名ですが、実は一部…
0. はじめに 今回は行列木定理(Kirchhoff's theorem)の証明を紹介してみようと思います。 行列木定理とは、全域木の個数の数え上げに関する定理です。証明方法はいくつかありますが、今回は漸化式を用いた全域木の個数の数え上げとの対応を見ることで定理を…
