Home

具体例での説明2


図1図2

図1の Grötzsch のグラフ で試してみます。(Grötzsch は グレッチュ と読むようです)図1 のように 4色で彩色できますが、3色では彩色できない臨界グラフです。11個の頂点と20個の辺で構成され、3点の完全グラフを含まず、かつ平面的なグラフではありません。

頂点0 に隣接する頂点の集合を H とします( H = {1, 2, 3, 4, 5} )。頂点0 と 頂点0 の辺を取り除いたのが図2です。

着色の条件X, Y を定義します。

具体例での説明 と同じ方法で計算します。

K4∧R は 9,842項になり、そのうち k∧K4∧R は 3,767項です。 (¬k)∧K4∧R は 6,075項です。

射影をとって重複する項を取り除くと Σ(k∧K4∧R) は 2,547項に、Σ((¬k)∧K4∧R) は 3,676項になります。

Σ(k∧K4∧R) に含まれていない Σ((¬k)∧K4∧R) の項は 2,571項です。その中で1の立ち方が極大となっているものが、420項あります。その一部を表にしました。'_' はグラフに含まれていない辺です。

着色の条件 X, Y の差分の表(極大の一部)
2345678910
112123123412345123456123456712345678123456789
___________0__00_0__0_1_0__1__1_1__01__1_1__0
___________0__00_0__0_1_1__1__1_1__01__0_1__0
___________0__00_1__0_0_0__1__1_1__11__1_1__0
___________0__00_1__0_0_1__1__1_1__11__0_1__0
___________0__00_1__0_1_0__0__0_1__11__1_1__0
___________0__00_1__0_1_0__0__1_1__01__1_1__0
___________0__00_1__0_1_0__1__0_1__01__1_1__0
___________0__00_1__0_1_0__1__1_0__11__1_1__0
___________1__11_1__0_0_1__0__1_0__00__0_1__0
___________1__11_1__0_0_1__0__1_0__00__1_0__0
___________1__11_1__0_0_1__0__1_0__01__0_0__1
___________1__11_1__0_1_0__0__0_0__00__1_0__1
___________1__11_1__0_1_0__0__0_1__10__1_0__0
___________1__11_1__0_1_0__0__0_1__11__0_0__0
___________1__11_1__0_1_0__0__1_0__00__1_0__0
___________1__11_1__0_1_0__0__1_0__01__0_0__1

集合H の中に3点の完全グラフをつくる辺の縮約が 420通りあることになります。表の1番上と下の縮約を図にしました。点線の辺が縮約する辺(負の辺)です。

図3図4

なお、図1の Grötzsch のグラフは6点の完全グラフに縮約する方法が2つあります。図5と6がそれです。両方とも点対称で、互いに裏返しの関係にあります。

図3図4


420通りある集合H の中に3点の完全グラフをつくる辺の縮約ですが、5次2面体群D5 の作用で重なるものを1つにまとめ、図にしてみました。44通りになりました。そのうち 線対称になるのは 26, 27, 30, 32 の4つです。対称になっているほうが、きれいに収まってる感じがしないでもありません。

001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044


Home