|
http://ja.wikipedia.org/wiki/四色定理 より
「一般に種数 g≧0 の閉曲面(解かりやすく言えば、孔がg個あるドーナッツ)を塗り分けるのに最低限必要な色の数は、1890年にヒ‐ウッドによって
式1 ([]はガウス記号)
と予想された。g≧1に対してこの予測が正しいことは、リンゲルとヤングスにより1968年に証明されていた。四色定理は、g=0の場合に対する証明を与えたことになる。」
この証明はコンピューターによるものしかないようですね。。。しかも、数学者の間では美しくないともっぱらの評判らしい、、、でも、誰も別な解法を示せてないという代物。。。
「歴史
色分けした世界地図。海と南極を含めて6色で塗り分けられている。
地図を製作する際には国境線を接する国は別の色で塗らなくてはならないので、地図制作業者の間では数百年前から経験的に知られていた。1852年に法科学生のフランシス・ガスリーが数学専攻である弟のフレデリック・ガスリーに質問したのを発端に問題として定式化され、19世紀後半になって数学者がその話を聞いて証明を試みたが、多くの数学者の挑戦をはねのけ続けていた。
1879年、アルフレッド・ブレイ・ケンプによる証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヘイウッドにより不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。そして、この問題は、グラフ理論における最も有名な未解決問題となった。
1976年に ケネス・アッペル (Kenneth Appel) とウルフガング・ハーケン (Wolfgang Haken) はコンピュータを利用して、本定理を証明した。しかし、あまりに複雑なプログラムのため他人による検証が困難であることや、コンピュータの誤りの可能性を考慮して、この証明を疑問視する声があった。その後、プログラムの改良が進められており、現在、四色問題の解決を否定する専門家はいない。
四色定理は実用的には地図作製だけでなく、携帯電話の基地局配置にも応用されている。周波数の同じ電波同士で混信してしまうFDMA・TDMA方式の携帯電話システムでは、隣接する基地局同士に同じ周波数を割り当てないように、塗り分けをしている。・・・
アッペルとハーケンはコンピュータによる実験を繰返し、プログラムを何度も書き換えながら、可約なグラフから成る約2000個のグラフからなる不可避集合を求めた。当時の最高速のスーパーコンピュータを1200時間以上使用したといわれている。
複雑に思える問題に対して斬新な観点から見るなどして得られた比較的短い証明(解答)を、エレガントな証明(解答)と言うことがある。四色定理の証明は、これと対極にあるものとして若干揶揄を込めて「エレファント(象)」な証明とも言われた。5色による塗り分けが可能であることの証明が簡潔なものであるのと対照的である。
その後アルゴリズムは改良されたが、現在でもコンピュータを使用しない証明は得られていない。またコンピュータを使う事以上に、証明の構成法自体が四色定理の解決に特化されており、他の問題との関係性に乏しいことも数学者の間で人気がない理由となっている。
なお、ハーケンは四色問題以前にはポアンカレ予想に挑戦していた時期があり、ハーケン多様体という3次元トポロジーの用語に名をとどめている。
トーラス(円環、いわゆるドーナッツの形)上のグラフは、7色で彩色可能である。・・・」
ヒーウッドによる最初の式はどうやって得られたのかを知りたいですよね。。。
だって、この式ってエレガントじゃないですか♪
画像1:四色に塗り分けられている
「四色定理(ししょくていり/よんしょくていり)とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。但し飛び地のような領域は考えない。実際の行政区分で飛び地があったとしても飛び地とその飛び地の所属する本国は関連せず、別の色であってもよいとする。解決前は四色問題と呼ばれており、未解決の期間が長かったため現在でも四色問題と呼ばれることがある。これは、グラフ理論において平面グラフは4彩色可能であるということと同値である。四つの領域が互いに接しているような地図が存在するので、3色では不可能である。この問題は球面上のグラフで考えても同値である。問題を双対グラフに置き換えることによって、頂点を彩色することに帰着される。四色定理の示すように領域の塗り分けが有限の色数で必ず可能となるのは平面(二次元)以下の次元までであり、三次元以上では領域の取り方次第でいくらでも色数が必要となってしまうようになる。」
http://en.wikipedia.org/wiki/Four_color_theorem より
「Generalizations
画像2:By joining the single arrows together and the double arrows together, one obtains a torus with seven mutually touching regions; therefore seven colors are necessary
画像3:This construction shows the torus divided into the maximum of seven regions, every one of which touches every other.
One can also consider the coloring problem on surfaces other than the plane. The problem on the sphere or cylinder is equivalent to that on the plane. For closed (orientable or non-orientable) surfaces with positive genus, the maximum number p of colors needed depends on the surface's Euler characteristic χ according to the formula・・・式2
,
where the outermost brackets denote the floor function. The only exception to the formula is the Klein bottle, which has Euler characteristic 0 and requires 6 colors. This was initially known as the Heawood conjecture and proved as The Map Color Theorem by Gerhard Ringel and J. T. W. Youngs in 1968.
Alternatively, for an orientable surface the formula can be given in terms of the genus of a surface, g:・・・最初の式
For example, the torus has Euler characteristic χ = 0 (and genus g = 1) and thus p = 7, so no more than 7 colors are required to color any map on a torus.・・・
Non-contiguous regions・・・画像4
In the real world, not all countries are contiguous (e.g. Alaska as part of the United States, Nakhchivan as part of Azerbaijan, and Kaliningrad as part of Russia). If the chosen coloring scheme requires that the territory of a particular country must be the same color, four colors may not be sufficient. For instance, consider a simplified map:
In this map, the two regions labeled A belong to the same country, and must be the same color. This map then requires five colors, since the two A regions together are contiguous with four other regions, each of which is contiguous with all the others. If A consisted of three regions, six or more colors might be required; one can construct maps that require an arbitrarily high number of colors. 」
* contiguous=連続
実際はいろんな飛び地もあるわけだから、、、どんな地図も4色で塗れるってわけじゃないようですね。。。^^;
Euler characteristic χ っての分かればまた載せますが、、、m(~~)m
|