組合せとグラフの理論(塩田)第4回 (2) 命題ひとつ

命題ひとつ

 次の命題は次回の一筆書きに使います:
Prop.3 閉じた小道 $T$ は閉路に分割できる。
Ex.4 例えば次のグラフの赤線のような閉じた小道 $T$

のように分けることができます。 ( 一通りとは限りません。)

Prop.3 の構成的証明 $T$ を
$T:v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_n$
とし、$v_0$ から出発して訪問回数が最初に2回になる頂点を
$v_i = v_j$ ( $i \lt j$ )
とします ( $v_n=v_0$ なのでこのような頂点が必ずあります ) 。このとき、
$C:v_i \rightarrow v_{i+1} \rightarrow \cdots \rightarrow v_j$
は $T$ に含まれる閉路になります。$T$ から $C$ を取り除いて
$\require{color}$ $T':v_0 \rightarrow \cdots \rightarrow \textcolor{red}{v_i \rightarrow v_{j+1}} \rightarrow \cdots \rightarrow v_n$
という歩道 $T'$ を作ると、これは $T$ より短い閉じた歩道になります。 ( $v_i=v_j$ なので $v_i$ と $v_{j+1}$ は隣接しています。) 帰納法の仮定より $T'$ は閉路に分割できるので、それらと $C$ と合わせれば宜しい。(証明終)

 Ex.4 では図の赤い頂点が最初に訪問回数が2回になります。
従って $C$, $T'$ は
となります。 $T'$ に対して「構成的証明」を再帰的に適用すると図の閉路 $C'$ がみつかり、 $T'$ から $C'$ を取り除いた $T''$ が閉路になっているので、これで分割が終了します。
プログラミングのために大切なこと 
  • プログラミングをするためには、単に可能性を証明するだけでは駄目で、構成的証明が必要です。
  • さらに、それが数学的帰納法で書いてあれば、再帰的プログラミングで実装することができます。