グラフ理論について、今のところわかったこと
任意のグラフをGとし、その彩色数をとあらわす。 1点uを加えG'とするとき、その接続数がk未満の場合には必ず
が成立する。
証明
であるGからk未満の点を選択するとき、uはかならずk色の中から彩色の色を選択できる。 よって上記が成りたつ。
(証明終わり)
任意のグラフをGとし、その彩色数をとあらわす。 1点uを加えG'とするとき、その頂点が全点に接続する場合には必ず
が成立する。
証明
であるGに頂点uを加え、全点に接続するならば、uは必ず全色に接続し、k+1色目が必要になる。
もしであるなら、彩色数が彩色できる最小の色数という前提に反する。
またで十分であり、
にはならない。
(証明終わり)
上記より
- 頂点数v, 彩色数kをあたえられたとき、接続数をk未満とする頂点を追加する操作を繰り返すことで、頂点数vで彩色数k以下を満たすグラフを作ることができる。
- vがkに対し、十分大きい時、頂点数v,彩色数kのグラフを作成できる。
- 無向グラフの頂点を適当に順序付けして、その任意の2頂点i,j (i < j)に辺があるとき、jからiに対し向きをつける。全ての頂点に対し、この出力辺をk本以内にできるとき、k+1彩色可能。ただし彩色数(Chromatic number)と一致するとは限らない。
- 上記からn正則グラフはn+1彩色可能、ただし彩色数(Chromatic number)と一致するとは限らない。
- ピーターセングラフがわかりやすい例
多分これは正則グラフではBrooksの定理と一致して、一般のグラフでは上限をよく押さえつけるものになるかな。
Brooks' theorem - Wikipedia
完全2部グラフKi,jを彩色した色クラスをそれぞれ閉路にしたとき(i,j >= 2)
- その彩色数は4(i,jが共に偶数),5(i,jが偶数、奇数),6(i,j共に奇数)になる。
偶閉路が2彩色、奇閉路が3彩色できることによる。
完全2部グラフKi,jを彩色した色クラスを完全グラフにしたとき
- その彩色数はi+jになる。
Ki+jと同一なことによる。
奇閉路に一点加えて彩色数を4とするためには全点に接続しないといけない。
俺の中でP=NPの機運が高まっている。
彩色数判定へのアプローチ
最初は彩色数kのグラフは2部グラフマッチングか最大流にできるとおもっていたのですが、制限付きナップサック問題かなにかに帰着できそうな気がしています。
たしかに組み合わせ問題なのでナップサック問題になってもおかしくなさそうです。
現在、v,e,kのみの数値でのプロトタイプを作成しています、ピーターセングラフはちゃんと3とでますが、2部グラフKn,mが2で出ません。
ただしある程度法則性があってn = mのときnででますし、m = n+1のときmででます。m = n + 2のとき、(m + n) / 2ででていて、完全2部グラフは完全グラフ内に含まれる。というのが仮説としてでてきました。
3彩色問題はヒューリスティックな感じの判定プログラムはつくれそうな気がします。
ただ理論的裏付けがなく、それが判定式となるのかはまだまだ研究中です。
完全グラフのマイナー
完全グラフばかり考えていたのですが、マイナーを考えないと本質にたどりつけなさそうなので考えています。
Kn を彩色数を変えずにKmだけ分離していく(強連結を置換していく)には、完全2部グラフが必要になる。
(片方はmだけど、もう片方が、m+1かn-1か、それともm + n / 2みないなものなのかが不明)
みたいな感じです。
四色定理の証明
変更しました。
四色定理から求められる平面グラフの性質
交差のない平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、 且つ、グラフ全体を4彩色する塗り方がある
交差のない平面グラフGにより構成される面Fの内、任意の面fを構成する閉路をCfとする。 このCfを3彩色し、Gを4彩色する方法が必ず存在する。 Gに点uを加えて、G'を作るとき、uは必ずある面f内に配置される(グラフの外も面と考える)。 この時fを構成する閉路Cfが必ず4色必要とされる場合、uからCf上の4色の点に 辺を作成したG'は必ず5色必要となり、四色定理に反する。
四色定理の別証明
四色定理はすでに証明済みであるが、上記の性質を仮定し、帰納法をもちい証明する。
四色定理が成立するためには、下記を証明すればよい。
交差のない平面グラフは必ず4色で彩色可能 <=> 任意の閉路を3色以内で彩色し、全体では4色となる彩色組み合わせが存在する。
頂点数nで交差のない任意の平面グラフGについて、 任意の閉路を3色とし、全体では4色となる彩色組み合わせが存在する。と仮定する。
G = K3の場合、1点加えたG'は必ず各閉路は3色以内で彩色可能で、 全体としては4色で彩色できる。(4色を必ず必要とするのはK4)
またG = K4に1点加える場合も同様である。
頂点数nの任意の交差のない平面グラフGに頂点uを加えG'とする場合に、 uを追加する面をfとし、その閉路をCfとする。 仮定により、Cfは3色で彩色することが可能である。
面fに頂点uを追加し、uからCf内の点に接続する。 Cfが3点しかない場合、どのように接続しても、新しくできた閉路は3色以内で彩色できる。 またCf外の彩色の組み合わせにも影響しない。
Cfが4点以上で異なる3色に接続する場合、4色目が必要で4色の閉路ができるが、 4色目は接続した部分と交換可能であり、新しくできた閉路を3彩色とすることが可能である。
交換できる理由について説明する。
この接続する3色が4色目と交換できない場合(接続する3色の組合せが1種類しかなく、且つ4色目と交換不可能な場合)、
閉路上の3色を1,2,3、新しく追加した色を4とし、4は1,3と接続するとすると,1 - 2,3,4 / 2 - 1,3,4 / 3 - 4, 2, 1が固定的に必要になる。 上記条件はK4で可能であるが、K4では交換可能である。 閉路の背後に必ずK3,K4をつなぐK3_3が必要となる。
クラトフスキー(Kuratowski)の定理により、これは交差のない平面としては存在できない。
またCf以外の閉路を3彩色した場合にはこのCfの交換可能である点が別の色となり、 やはり4彩色可能な組み合わせがある。よって任意の閉路を3彩色し、全体を4彩色可能である。
よって交差のない平面グラフは4色で彩色可能である。
(証明終わり)
