広島工業大学紀要研究編
第 43 巻（2009）pp.331-337

論文

多面体の塗り分け
殿塚

勲＊・村上智秋＊＊（平成 20 年 10 月 10 日受理）

Polyhedron Coloring
Isao TONOZUKA, Chiaki MURAKAMI（Received Oct. 10, 2008）

Abstract
This paper deals with the coloring of polyhedrons. The famous four-color theorem
comes into effect for polyhedrons as well as the 2-dimensional maps. However, themore the faces of polyhedrons the more complicated, and it becomes almost
impossible to solve the four-color problem. A systematic procedure or an algorithm
is needed for this problem. Our proposals on the problem are applied to the regularpolyhedrons and delta polyhedrons.

Key Words: polyhedron, coloring, four-color problem, four-color theorem, regularpolyhedron, delta polyhedron

かし，その証明は多くの数学者から正しいものと評価され1 はじめにている［1］。

地図を色で塗り分けをするとき，隣接の国が相異なる色

ここでは多面体の塗り分けを扱い，平面の地図と同様にになるようにする問題を考える。ここで一つの国には飛び隣接の面が同じ色にならないように塗り分けるものとする。

地は無いものと仮定する。このとき地図を塗り分けするにこの問題は立体である多面体を平面に射影すれば，多面際し，何色あればこの要求を満たすことができるであろう

体の塗り分けは平面上の地図の塗り分けとほぼ同じ扱いがか。この問題は実用的な関心もあり長い歴史の中で，経験できる。（Cauchy）したがって「四色定理」により与えら的に 4 色あれば隣接の国が同じ色にならないように色分けれた多面体を 4 色以内で塗り分けることができるのは当然できることが確からしいことが分かってきた。（ガスリーであるが，その具体的な実現方法は自明ではない。多面体（1852））

が複雑になると 4 色以内での塗り分けは行き当たりでは不この問題を四色問題［1］という。この問題にはプロだけ可能であるほどの困難さが生じる。

でなくアマチュアも興味を抱くこととなり，多くの数学者

ここでは実際の色分け作業のために系統的な手順を示や好事家が参加したが，4 色以内で塗り分けができる，とし，さらに多面体により 2 色で済む場合，3 色で済む場合，いう「四色定理」の最終的な証明はアッペル，ハーケン

4 色を必要とする場合などについても考察する。

（1976）まで実に 100 年以上の道のりがあった。しかも最多面体には 5 種類の正多面体，13 種類の準正多面体［4］，終的な証明はコンピュータを駆使した「力技」に依ったの8 種類のデルタ多面体，その他 Zalgaller 多面体（すべてで，多くの数学者からは反感をもたれることとなった。しの面が正多角形である凸多面体，92 種）［3］［2］やそれらの* 広島工業大学情報学部知的情報システム学科** 広島工業大学情報学部知的情報システム学科学部生

―331―

殿塚

勲・村上智秋星形化などが知られているが，ここでは正多面体とデルタり，多角形の周囲を順に番号づけられているものとする。

多面体（すべての面が正三角形の多面体）に限っておく。

また面 j の多角形の頂点の数は

なお以下の考察では，多面体を 2 色（3 色，4 色）で塗m [j] [0]り分けができれば 3 色（4 色，5 色）以上でも塗り分け可に格納する。

能である，ということを自明のこととする。

2 基礎的な考察

1 つの面に隣接する面の番号と色番号（整数値）

c [j] [k] (j = 0, 1, 2, gnm - 1),(k = 1, 2, g, n j )多面体の塗り分けは（2 次元の）地図の塗り分けと基本的には同じ問題である。多面体は角点（かどてん），陵線（りょうせん），面などを属性として持つ。角点につながる面 j を構成する頂点の数と隣接する面の数 n j は同じなの

陵線の形から図 1，図 2，図 3 などに分類し，多角形の周で， m [j] [k]と同じインデックスを用いている。 j を与えりの陵線の形から図 4，図 5，図 6 に分類する。以下にはたときの (k = 1, 2, g, n j ) に対する c [j] [k]は面 j に隣接す正多面体に含まれる図の番号と塗り分けに必要な最低の色る k 番目の面を表わし数をまとめた。

c [j] [0] (j = 0, 1, 2, ...nm - 1)

正四面体

図 1，図 44色

正六面体

図 1，図 53色

正八面体

図22色

正十二面体

図 1，図 64色正二十面体

図33色には面 j の色番号を格納する。したがって面 j に隣接する面 k の色番号は

c [c [j] [k]] [0] (j = 0, 1, 2, gnm - 1),(k = 1, 2, g, n j )となる，すなわち面 j に隣接する面 k の番号を u = c [j] [k]とおくと， j に隣りあう面 k の色番号は c [u] [0]となる。

多面体の塗り分けに必要な色の種類は上の表の色数を下限とする。ここで図 4 は 4 色問題の発祥となったといわれる
ド・モルガン［1］の手紙に現れる図 7 と同型であって，こ多面体のグラフィックス表示
多 面 体 を グ ラ フ ィ ッ ク ス 表 示 す る に は 上 記 t [i] [r] ，の手紙には「塗り分けのために 5 色以上が必要とされる地m [j] [k]， c [j] [k]があれば可能である。

図は作れそうにない」とある。ド・モルガンにこのことをこのうち t [i] [r]， m [j] [k]の 2 つは，Zalgaller 多面体に指摘したのは当時の学生のフランシス・ガスリーであり，ついては小林等［3］により計算されて，ファイルの形で提彼が 4 色問題の考案者とされている。

供されているので，これを利用する。

3 多面体を記述するデータ構造と塗り分けアルゴリ

c [j] [k] に 関 し ， k = 0 を 除 い た (j = 0, 1, 2, ...nm - 1) ，ズム
頂点の座標値（実数値）(k = 1, 2, ..., n j )についてはデータ m [j] [k]を用いて容易に求めることができる。以後面 j の色番号

頂点座標や面などを配列により表現する際，変数名とインデックスを t i, r のように書くべc [j] [0] (j = 0, 1, 2, ...nm - 1)

きであるが，ここでは C 言語によるプログラミングを念を，隣接する面の色が同じにならないように求める方法に頭におき

t [i] [r] (i = 0, 1, 2, gnt - 1),(r = 0, 1, 2)

ついて考える。
色の塗り分けアルゴリズムの例のような書き方をする。

正六面体の面の塗り分けを例として，塗り分けアルゴリズムを表 1 により説明する。

ここで i は多面体の頂点につけた番号であり，頂点の数6 つの面には 0 から 5 まで番号をつけ，それぞれの面に隣は nt 個とする。 r はその 3 次元座標 x ， y ， z の成分である。

接する面の番号の表（隣接面（1））を作る。0 面から始めて順に 5 面まで色を定めてゆくので，それまでに色が決定

面を構成する頂点の番号（整数値）

された面番号だけを記した表を隣接面（2）として作成した。

m [j] [k] (j = 0, 1, 2, gnm - 1),(k = 1, 2, g, n j )色は 4 種あればよいので色の番号を 0，1，2，3 とする。
0 面の色は任意なので，例えば色 0 とする。1 面の色は隣多面体の面の数を nm 個とし，面につけた番号を j とする。

あう 0 面と異なるように決めれば任意でよいので色 1 とす

k はその面を構成する多角形の n j 個の頂点の座標番号である。2 面は 0，1 面の色 01 と異なるように色を決めてばよ―332―

多面体の塗り分け

表 1 ：正六面体の色決定

面番号

隣接面（1）

隣接面（2）

色（数値は面の順につけた色番号）

0235101054202143010012324502001210123

4215321301210

0121301230

50341034012102012103

012132011012302

表 2 ：正多面体の立体図と射影図

正多面体

立体図

射影図

塗り分けに必要な色の種類

正 4 面体図 9a図 10a4

正 6 面体図 9b図 10b3正 8 面体

図 9c

図 10c2

正 12 面体

図 9d図 10d4

正 20 面体

図 9e図 10e3

いので 2，3 の 2 種の色があるが，2 に固定しても一般性

5. 4.を j = nm - 1まで繰り返す。

を失わないので面 012 の順に色は 012 となる。次に 3 面は上記は，これから面 j の色を決めるとき，「その隣接面2，0 面の色と異なる色を選ぶので 1，3 の 2 種の可能性がの中に既に決定されたものがあればそれとは異なる色を選あり 0121 と 0123 となる。

ぶ」を定式化したものであり，面 0, 1, gnm - 1の順に色は以下同様にして最終的に色の欄の 5 面の色まで決定でき，このうち 012102 が 3 色による塗り分けであり他は 4c [0] [0], c [1] [0], ...c [nm - 1] [0]色が必要となる。

が定まる。

3 色で塗り分けが可能であれば，4 色以上を用いても塗り分けが可能であることは自明なので最小数の色での塗り4 2 次元平面への射影分けを探す。
色の塗り分けアルゴリズム

上の例のように色の塗り分け多面体の塗り分けをしてこれをそのまま見ても裏面が見だけであればデータ c [j] [k]があればよい。 c [j] [k]は面番えない。そこで多面体を 2 次元平面に射影して全ての面が号 j に隣接する面の番号(k = 1, 2, g, n j )である。

見えるようにする。複素関数論では複素平面の全体を中心
11d 0, 0, n，半径 の球の表面に対応させることが行われる。
22（Riemann 球）

1. 面番号 0, 1, 2gの順に色を決める。面 j の色を決める
ときそれより前に決めた面の色だけに影響されるので，表 1 の隣接面（1）のうち既に決まった色を隣接面+（2）（ c [j] [k]と書く）とし，これとは異なる色を選ん2

x2+ y2+ dz - 1 n = d 1 n222（1）

この球面の頂点(0, 0, 1) から球面上の点(x, y, z)を突き抜
けて z = 0 平面に向けて直線を引くと平面(X, Y)の座標はで次の面の色を決定する。
2. 面 j = 0 の色を c [0] [0] = 0 とおく。

X=

3. 面 j = 1の色は隣接面（2）+x ，Y = y
1-z
1-z（2）

c [0] [k]，(k = 1, 2, g, n0 )を調べ，面 0 と異なるように対応し，(0, 0, 1)を除いて球面と平面が1 : 1に対応する。に色番号 c [1] [0]を選ぶ。

これを多面体に適用するために，多面体の座標中心が(0, 0, 0)，半径 1 の球に納まるように規格化し，この中2
心を z 方向に 1 持ち上げたうえで（1）を適用して 2 次元2の(X, Y)平面上に射影する。ここで多面体中で最も z = 1に+

4. 面 j の色は c [j - 1] [k](k = 1, 2, ..., n j - 1)を調べ，面 j - 1 と異なるように色番号 c [j] [0]を選ぶ。
―333―

殿塚

勲・村上智秋

表 3 ：デルタ多面体の立体図と射影図

デルタ多面体

立体図

射影図

塗り分けに必要な色の種類

デルタ 6 面体

図 11a図 12a3デルタ 10 面体

図 11b図 12b3デルタ 12 面体

図 11c

図 12c3デルタ 14 面体

図 11d

図 12d3デルタ 16 面体

図 11e

図 12e3近い面を(X, Y)平面に平行になるように選ぶとき（これを面は外部の領域に対応する。

基準面に選ぶ），(X, Y)平面に射影された面の数は多面体

デルタ多面体とはすべての面が正三角形でできている多の面の数より 1 だけ少ない図形となる。（図 8）面体で 4，6，8，10，12，14，16，20 の 8 種類があり，こなお，多面体の形によってはうまく射影面の数が 1 少なのうち 4，8，20 は正多面体であって表 2 に含まれるので，い図形とはならないこともあり，このときは（1）ではなし

残りのデルタ多面体を表 3 に示した。に関数

X = x (1 + az)， Y = y (1 + bz)

デルタ多面体の立体図は図 11a 〜図 11e であり，その射（3）影図を図 12a 〜図 12e に示した。デルタ多面体では， n = 4の正四面体を除きすべて 3 色で塗り分けが可能である。

を用いてパラメータ(a, b)をうまく選んできれいな 2 次元

参考文献

射影図を作ることもある。

［1］ロビン・ウィルソン，茂木健一郎訳，四色問題，新潮

5 まとめ社（2004.11）

5 種類の正多面体は表 2 のように，正六面体は 3 色，正［2］関口次郎，多面体の数理とグラフィックス，牧野書店

八面体は 2 色，正二十面体は 3 色で塗り分けができるが，正四面体と正十二面体は 4 色必要である。これは 2.基礎的（1996.2）［3］小林光夫・鈴木卓治「正多角形を面にもつすべての凸な考察での結果と一致する。

多面体の頂点座標の計算」電気通信大学紀要，第 5 巻

図 9a 〜図 9e は正多面体の立体図であり，図 10a 〜図10e はそれらの 2 次元への射影図である。正多面体の面数（1992），p147-184［4］一松信，正多面体を解く，東海大学出版会（1983.6）

を nとすると，射影図には n - 1の領域があるが，最後の n―334―

多面体の塗り分け

図1

図2図3図4図5図6図7

図 9a図8図 9b―335―

図 9c

殿塚

勲・村上智秋

図 9d図 9e図 10a図 10b図 10d図 10e図 11a図 11b―336―

図 10c図 11c

多面体の塗り分け

図 11d図 11e図 12a図 12b図 12d図 12e―337―

図 12c