組合せとグラフの理論（塩田）第15回 (3) 確率的手法
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\card}[1]{\left|\,#1\,\right|}$
グラフの不変量の間の関係
グラフの連結度、辺連結度、最小次数の間には
連結度 $\leqq$ 辺連結度 $\leqq$ 最小次数
という不等式が成り立っていました ( 第4回 )。
したがって最小次数が小さいグラフでは連結度も辺連結度も小さい、ということがわかります。
このように、グラフの不変量の間にはどんな関係があるのか、興味が持たれます。
例えば
Def.
グラフに含まれる閉路の長さの最小値を「内周」と呼ぶ。
この内周について
Question
内周と彩色数の間には何か関係はあるか？
という問を考えてみましょう。
いくつかのグラフで内周と彩色数を書き出してみると
| 内周 | 彩色数 |
| $K_n$ | 3 | $n$ |
| $C_n$ | $n$ | 2 or 3 |
| $Q_k$ | 4 | 2 |
| $K_{m,n}$ | 4 | 2 |
| ピータスングラフ | 5 | 3 |
| 正十二面体グラフ | 5 | 3 |
感覚的には
内周が大きい $\Rightarrow$ 辺は少ない $\Rightarrow$ 彩色し易い $\Rightarrow$ 彩色数は小さい ?
という気がしなくもありませんが ...
確率的手法
「グラフの集合」に確率を導入する「確率的手法」を使って上の問に対する答えが得られています：
Th.(Erdos)
任意の整数 $k$ に対し、内周も彩色数も $k$ より大きいグラフが存在する。
$K_n$ のように内周は小さく彩色数の大きいグラフもあれば、
$C_n$ のように内周は大きく彩色数の小さいグラフもあり、
内周も彩色数も共に大きいグラフもある。
結局、内周と彩色数には関係は無かった、というオチです。
Erdos の定理の証明方針 は
- 頂点数 $n$ のグラフ全体の集合に「確率」を定義する。
- 「 ( 内周 $\gt k$ ) かつ ( 彩色数 $\gt k$ ) 」となる確率が $n \rightarrow \infty$ のとき 0 より大きいことを示す。
というものです。同じ手法で色々な定理が作られています。