Home

具体例での説明４　完全グラフへの分解

次のグラフの彩色には４色が必要十分です。

0 1 2 3 4 5 6

頂点0と3を結ぶ辺 e0,3 がありませんので、e0,3 を付け足したグラフと、¬e0,3 を付け足したグラフをつくります。

0 1 2 3 4 5 6 0 1 2 3 4 5 6

彩色に４色を必要という性質を維持しつつ、無くてもよい頂点と辺を取り除きます。ただし、e0,3 または ¬e0,3 を残さなければなりません。（この方法が複数ある場合は、そのうちの任意の１つでかまいません。）

0 1 2 3 5 6 0 1 2 3 4

グラフを論理式とみなす（グラフに含まれる辺の論理和とします。点線の辺は負の辺とします）と次の恒真式になります。

0 1 2 3 5 6 0 1 2 3 4 0 1 2 3 4 5 6 ∧ →

同様に分解を進めます。

0 1 3 6 0 1 2 0 2 3 5 0 1 2 3 5 6 ∧ ∧ →

0 1 3 0 1 2 4 0 2 3 0 1 2 3 4 ∧ ∧ →

結果、次の６つの完全グラフに分解することが出来ました。３つの４点の完全グラフと、３つの３点の完全グラフです。３点の完全グラフは２つの辺が負の辺になっています。

0 1 3 0 1 2 4 0 2 3 0 1 3 6 0 1 2 0 2 3 5

逆に、こうした４点の完全グラフと３点の完全グラフをすべて用意しておけば、すべての３色で彩色不可能なグラフがブール代数の計算で導くことができるのではないか、という考えになってきます。

“負の辺”の導入と、グラフを辺の論理和とみなすことで、ブール代数で扱うことができます。ブール代数の知識や、普通の代数からのアナロジーで研究することができます。

Home