院試勉強にもそろそろ飽きてきたので、気分転換に数理情報学専攻の専門数学の予想問題を作ってみました。計数工学科内では有名な（？）話題に関する問題ですが、ちょっとマニアックなので、暇な人は解いてみてください。難易度は難しめ（&分量多め）だと思い…

今回は、すべての頂点の次数が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困難な問題でもグラフを木に限定すると多項式時間で解けたりする話は有名ですが、実は一部…