具体例での説明３

Petersen（ピーターセン、あるいはペテルセン）グラフです。10個の頂点と15個の辺で構成され、平面的なグラフではありません。彩色には３色が必要十分です。

着色の条件を設定します。

K₅∧R：全体を 4色以内で着色する。
K₆∧R：全体を 5色以内で着色する。
K₇∧R：全体を 6色以内で着色する。

計算はパソコン上のプログラムで実行しました。愚直にすべての着色で辺の真理値を求め整理する方法です。

各論理式を加法標準形式に展開したときの最小項の数を表にまとめます。

各論理式の最小項の数
K₅∧R	43,947	Σ(K₅∧R)	8,575
K₆∧R	86,472	Σ(K₆∧R)	8,581
K₇∧R	109,299	Σ(K₇∧R)	8,581

Σ(K₆∧R) の最小項で、Σ(K₅∧R) に含まれないものが、６項あります。それを表にしました。'_' はグラフに含まれていない辺です。すべて１の立ち方が極大となっています。

Σ(K₅∧R) にない Σ(K₆∧R) の最小項
2	3	4	5	6	7	8	9	10
1	12	123	1234	12345	123456	1234567	12345678	123456789
0	_0	__0	0__0	1____	_1____	__1__0_	___1_00_	____1_00_
0	_0	__1	1__0	0____	_1____	__0__0_	___0_10_	____0_01_
0	_1	__0	0__1	1____	_0____	__0__0_	___0_01_	____0_01_
0	_1	__0	1__0	0____	_0____	__0__1_	___1_00_	____0_10_
1	_0	__0	0__1	0____	_0____	__1__0_	___0_10_	____0_10_
1	_0	__1	0__0	0____	_0____	__0__1_	___0_01_	____1_00_

表の一番上のものを図にしたのが、図２です。点線の辺が縮約する辺（負の辺）です。表の２番目のものが図３です。後の４つは、図３を回転させることによって得られます。図２も図３と、グラフの対称性を考えれば同じものと見なせます。ピーターセングラフを５点の完全グラフに縮約する方法は本質的には１つしかありません。

Σ(K₇∧R) を計算してみましたが、最小項の数は 8,581 で、Σ(K₆∧R) と変わりありません。これは６点の完全グラフに縮約する方法がないことを意味します。

Home