４色問題
03/02/07 09:25 格納先: Mathematics
フリー百科事典『ウィキペディア（Wikipedia）』から４色定理の一部を引用します。
四色定理（ししょくていり／よんしょくていり）とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。但し飛び地のような領域は考えない。実際の行政区分で飛び地があったとしても飛び地とその飛び地の所属する本国は関連せず、別の色であってもよいとする。解決前は四色問題と呼ばれており、未解決の期間が長かったため現在でも四色問題と呼ばれることがある。
（中略）
1879年、アルフレッド・ブレイ・ケンプによる証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヘイウッドにより不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。そして、この問題は、グラフ理論における最も有名な未解決問題となったのであるが、1976年に ケネス・アッペル (Kenneth Appel) とウルフガング・ハーケン (Wolfgang Haken) によってコンピュータを駆使して証明された。しかし、あまりに複雑なプログラムのため他人による検証が困難であることや、コンピュータの誤りの可能性を考慮して、この証明に疑問視する声があった。その後、プログラムの改良が進められており、現在、四色問題の解決を否定する専門家はいない。
四色定理（ししょくていり／よんしょくていり）とは、いかなる地図も、隣接する領域が異なる色になるように塗るには4色あれば十分だという定理である。但し飛び地のような領域は考えない。実際の行政区分で飛び地があったとしても飛び地とその飛び地の所属する本国は関連せず、別の色であってもよいとする。解決前は四色問題と呼ばれており、未解決の期間が長かったため現在でも四色問題と呼ばれることがある。
（中略）
1879年、アルフレッド・ブレイ・ケンプによる証明が『アメリカ数学ジャーナル』誌上で発表された。この証明は妥当と見なされていたが、1890年になってパーシー・ヘイウッドにより不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。そして、この問題は、グラフ理論における最も有名な未解決問題となったのであるが、1976年に ケネス・アッペル (Kenneth Appel) とウルフガング・ハーケン (Wolfgang Haken) によってコンピュータを駆使して証明された。しかし、あまりに複雑なプログラムのため他人による検証が困難であることや、コンピュータの誤りの可能性を考慮して、この証明に疑問視する声があった。その後、プログラムの改良が進められており、現在、四色問題の解決を否定する専門家はいない。