四色問題の証明
- S Y
- 2021年7月23日
- 読了時間: 7分
更新日：2021年7月25日
0. 参考文献
[1]百科事典マイペディア
Copyright (c) Heibonsha Limited, Publishers, Tokyo. All rights reserved.
[2]彩色問題 大橋昌矢 ほか
1. 四色定理とは
任意の平面グラフにおいて、隣接する閉領域を塗り分けるのに必要な最低の色の数は四色であるだろうという予想があります。これを、四色問題と言います。1976年に、W.ハーケンとK.アッペルにより、コンピュータを用いて証明が完了しました。ところで、未だ、論理による証明はされていません。[1]ですが、証明した二人に敬意を表し、ここでは四色定理と呼ぶことにします。
2. 五色定理とは
平面グラフにおいて、隣接する閉領域を塗り分けるのに、5色あれば十分であるという定理です。1890年にパーシー・ヒーウッドにより証明されました。この際、オイラーの多面体の定理を用いました。[2]
3. 四色定理の証明
今回は、コンピュータを使わない方法で、四色定理を証明してみたいと思います。ご指摘がありましたら、コメントをお願いいたします。
3.1 この章で使用する図一覧
図1
図2
図3
図4
図5
図6
図7
図8
図9
図10
図11
3.2 非接続頂点数計上法
塗り分ける領域を頂点とし、接続の仕方を辺で書き直したグラフを考えます。この時、各頂点に、自身と辺で直接接続されていないような、頂点の個数を調べます。ただし、ひとつの辺も接続していない頂点(孤立頂点)については無視することとします。
図1を例に考えます。頂点A,B,C,Dはそれぞれ、頂点C,D,A,Bと互いに非接続な関係にあります。そのため、それぞれ、(1,1,1,1)個と計上できます。
図2を例に考えます。頂点A,B,C,Dはそれぞれ、頂点C,(NaN),A,(NaN)と互いに非接続な関係にあります。ここで(NaN)は空集合を意味します。以上から、それぞれ、(1,0,1,0)個と計上できます。
次に、計上した頂点数に対して少ない順にランキングします
図1の場合
1位：A,B,C,D
図2の場合
1位：B,D
2位：A,C
3.2 線形(閉曲線なし)の場合
線形の場合、図3を考えると良いでしょう。この図に対して、非接続頂点数計上法を行うと、次の結果が得られます。
(A, B, C, D, E, F, G) = (5, 4, 2, 5, 5, 4, 5)
ランキングすると、次の結果が得られます。
1位：C
2位：B,F
3位：A,E,D,G
この時、3位まであることに注意してください。
ここで、互いに1点だけで干渉するような、二つの線分とみなしてみましょう。
例
線分α：A→B→C→D
線分β：E→F→C→G
それぞれの線分について、非接続頂点数計上法を行うと、次の結果が得られます。
線分α：(A, B, C, D) = (2, 1, 1, 2)
線分β：(E, F, C, G) = (2, 1, 1, 2)
それぞれをランキングしました。
線分α
1位：B, C
2位：A, D
線分β
1位：F, C
2位：E, G
頂点Cについて、いずれの線分においても1位となっていることに気づきます。実は、線分の交点には多くの頂点が接続しているので、高順位になりやすいのです。
また、ランキングにおいて、最高順位である頂点は、他の頂点に対して制限をより多くかけることができます。反対に、順位の低い頂点は、低いほどグラフ全体の性質を強く示します。
すなわち、交点のような高順位の頂点から始めると、容易に塗り分けが可能となるのです。
線分の場合、頂点の次数は1または2です。そのためランキングでは2位までに全ての頂点がランキングされます。
このことから、以下の定理が得られます。
定理：塗り分ける面をグラフ化したとき、それが線分である場合は、高々2色で塗り分けられます。また線形においては、いくつかの線分が交わったものとみなせるので、これも高々2色で塗り分けられます。
3.3 閉曲線1周の場合(中心点なし)
3.3.1 観察
図4,5のような、いくつかの頂点が連なりひとつの閉曲線となったものを考えます。
この時、同じ位の頂点数の偶奇を調べます。
閉曲線であるから、頂点の個数にかかわらず、回転対称性が成立します。そのため全ての頂点は同率1位となります。
さらに、図4のように頂点数が偶数であれば、頂点を通らない直線で線対称な配置を実現することができます。この場合、線対称となる直線で分けたうちの一方は3.2で述べた線形となるので、2色で塗り分け可能であることがわかります。反対側についても、同様に2色で塗り分けることができます。ただし、選択するときに、それぞれの始点とそれぞれの終点が、互いに異なる色となるように気をつけなければなりません。
また、図5のように頂点数が奇数であれば、一つの頂点を通る直線で線対称な配置を実現することができます。この場合、直線が通らない頂点については、頂点数が偶数である場合と同様に考えられます。ところが、直線の通る頂点については、結果として3色目が必要となります。両端の色がそれぞれ異なるためです。
3.3.2 非接続頂点数計上法
頂点数が偶数であろうと、奇数であろうと、順位は同率1位となります。
3.4 中心を通らない閉曲線がひとつの場合(中心点あり)
3.4.1 観察
図6,7のような、いくつかの頂点が連なりひとつの閉曲線となったもので、かつその中心にもひとつ頂点があるものを考えます。
ここで、中心を通らない閉曲線とは、全ての頂点に接続している頂点(中心点)を経由しない閉曲線のことを意味します。
この場合、すでに中心の頂点に一色与えられているので、3.3での結果に、一色追加する必要があります。すなわち、閉曲線の頂点の数が偶数であれば3色、奇数であれば4色で塗り分けられます(条件3.4.1)。
ここで、次の定理を説明します。
定理
図8,9のように、中心点と接続しない頂点が存在するグラフの性質は、そのような頂点を横断して接続した閉曲線の性質と同様であります。すなわち、図8であれば、閉曲線A→B→C→D→G→AをA→D→G→Aに、図9であれば、閉曲線A→E→D→GをA→G→Dと見なして良いです。
証明
図8であれば、閉曲線A→B→C→D→G、図9であれば、閉曲線A→E→D→Gについて、中心点のない閉曲線と見なすことができます。図8であれば閉曲線A→B→C→D→Gについて、頂点数5個であるから3色必要、図9であれば、閉曲線A→E→D→Gについて、頂点数4個であるから2色必要です。以上の条件は条件3.4.1と同等かそれより弱いので、考えなくて良いです。
3.4.2 非接続頂点数計上法
中心点と接続しない頂点が最下位、中心点が一位、中心点と接続する頂点が2位となります。また2位または3位以内に全ての頂点がランクインします。(※1)
※1 3.6で証明します。
3.5 中心を通らない閉曲線が複数の場合(中心点あり)
図10のような、複数の閉曲線が重なっているものを考えます。(ABCDE, FGHIJK)この場合、いくつかの頂点は、3位以内に入らないことがあります。しかしよく見ると、3.4の「中心を通らない閉曲線がひとつの場合(中心点あり)」で説明したような閉曲線がいくつか重なって存在していることがわかります。つまり、中心点と接続している頂点を中心とする、閉曲線を見つけられます。
例えば、図10では点Oが中心となるのですが、それに接続している点Cは、BODHGの中心に、点AはFBOEKの中心になっています。それぞれ、条件3.4.1を与えていて、これが最も強い条件となっています。
このように、中心を通らない閉曲線が複数ある場合でも、中心を通らない閉曲線がひとつである場合(中心点あり)を与えるような頂点を見つけることで、同様に考えられます。
3.6 中心を通らない閉曲線がひとつの場合(中心点あり)において、4位以降にランクインする頂点は存在しないのでしょうか
以下の議論は、中心Oに対して頂点K, L, M以外の頂点が接続した場合も同様に考えられます。(※2)図11において、辺A, B, C, D, Eのいずれかを消去し、順位を変化させることを考えます。また、問題の性質上、頂点が一つの辺とも接続しないことは考えなくて良いです。さらに、辺は連続であるとします。
現状、非接続頂点計上法による値は以下の通りです。
以下の表は、辺を外した時に、各頂点の非接続頂点計上法による値がどのように変化するのかをまとめたものです。
頂点が孤立しないように気をつけて、外す辺を選択します。辺は連続であるようにする必要があります。
組み合わせは、次の通りです。
(1つ選ぶ)
A~E
(2つ選ぶ)
A・(C,D,E)
B・(C,D,E)
C・(D,E)
(3つ以上選ぶ)
孤立する頂点が現れるため、不適です。
非接続頂点計上法による値はそれぞれ次のようになります。
以上から、中心を通らない閉曲線がひとつの場合(中心点あり)において、4位以降にランクインする頂点は存在しないことがわかります。
※2
新たに頂点を追加することで、別のループが現れたり、ループに線形の図形が現れたりしますが、ループと、線形の図形を別々に捉えることで、頂点を追加する前の状態と同様に議論することができます。
4. まとめ
非接続頂点数計上法を用いて頂点をランキングすることにより、グラフの特性(何位以内にグラフの全ての頂点がランクインするのか)を掴みました。
また、非接続頂点数計上法の結果を、線形、ループ(中心点なし)、ループ(中心点あり)、ループ複数(中心点あり)に分類して考えました。すると、「頂点の計上結果の最下位が何位であるか」、「ループを作る頂点は偶数か、奇数か」に着目することで、何色で分けられるのかについての解を与えられることがわかりました。
さらに、全てのグラフの頂点について、形上結果は高々3位以内に入ることがわかりました。
また、3位以内に入り、かつ頂点数が奇数個である時の条件が最も強く、4色必要であることがわかりました。
以上から、次の定理を再確認できる。
「任意の平面グラフにおいて、隣接する閉領域を塗り分けるのに必要な最低の色の数は四色である。」
©︎2021 Yume Isioto
コメント