Loading article…
地球・月問題は、数学におけるグラフ彩色に関する未解決問題です。これは平面地図彩色問題（四色定理で解決済み）の拡張であり、 1959年にゲルハルト・リンゲルによって提起されました。[ 1 ]この問題の直感的な形式は、地球の各国が月面植民地を持ち、同じ色でなければならないという架空の未来において、地球と月の政治地図を彩色するために何色必要かというものです。数学的には、これは二平面グラフの彩色数を求める問題です。この数は少なくとも9、最大で12であることが知られています。
地球・月問題は、任意の数の惑星上の地図を彩色するという類似の問題にも拡張されています。この拡張では、色の数の下限と上限がより近くなり、互いに2つ以内の差になります。地球・月問題の実際の応用例の1つは、プリント基板のテストです。
地図彩色問題では、ユークリッド平面または位相的に等価な空間（地球表面上の国など）における有限個の単連結領域を、長さがゼロでない境界を共有する2つの領域が異なる色になるように彩色します。各領域に頂点、隣接する2つの領域に辺を作成することで、グラフ彩色問題に変換できます。これにより、頂点を彩色する平面グラフが生成されます。隣接する領域が異なる色を持つという要件に対応して、隣接する頂点（任意の辺の両端）が異なる色を持つ必要があります。4色定理によれば、結果として得られる平面グラフ（または任意の平面グラフ）は、与えられた領域の数に関係なく、最大で4つの異なる色を使用して彩色できます。[ 2 ]
1959年、ゲルハルト・リンゲルは曲面の彩色に関する著書を出版し、当時研究されていた四色問題と、トーラスやクラインの壺などの非平面曲面上の地図の彩色に関するヒーウッド予想の結果を概観した。[ 1 ]どちらも長年予想されていたが、当時は未解決だった。リンゲル自身は後に1968年のJWTヤングスとの論文でヒーウッド予想を証明した。[ 2 ] [ 3 ]四色定理は1976年まで証明されなかった。[ 2 ] [ 4 ]リンゲルの著書のもう一つのテーマは、1890年のパーシー・ジョン・ヒーウッドによる「帝国問題」に関するもので、各帝国が何らかの数を持つ地図の彩色に関するものだった。地球上の異なる地域（母国と植民地）。ヒーウッドが示したようにそしてリンゲルは後に1984年にジャクソンと共に証明した。、色は必要かつ十分である。[ 2 ] [ 5 ] [ 6 ] [ 7 ]おそらくこの問題と宇宙時代の幕開けに触発されて、リンゲルは地球と月の問題を、植民地が地球ではなく月にある帝国問題の変形として、著書に含めた。[ 1 ] [ 2 ]マーティン・ガードナーの定式化では、植民地は代わりに火星にある。[ 6 ]
リンゲルの地球・月問題では、地球上の各国には月面に対応する植民地があり、それらに同じ色を付ける必要がある。これらの植民地の境界線は、地球上の境界線の配置とは全く異なる可能性がある。各国とその植民地には同じ色を使用して国を着色し、地球上または月面で国境を共有する2つの国には異なる色を付ける必要がある。リンゲルの問題は、国境の配置に関係なく、すべての国を着色できることを保証するには、いくつの色が必要か、というものである。[ 2 ]リンゲルは、必要な色の数は少なくとも8、最大で12であることを証明し、8が正解であると推測した。[ 6 ]
繰り返しますが、同じ問題をグラフ理論の問題と同等に表現することもできます。国とその植民地の各ペアに1つの頂点があり、国または植民地間の隣接関係ごとに1つの辺があります。平面の場合と同様に、この変換の後、頂点に色を付けなければならず、各辺の端点には異なる色を付ける必要があります。この問題のバージョンで得られるグラフは、双平面グラフ、または同等に厚さ2のグラフです。これらのグラフの辺は、対応する2つの部分グラフが両方とも平面となるように、2つの部分集合（地球の隣接関係から来る辺と月の隣接関係から来る辺）に分割できます。数学的に言えば、リンゲルの問題は双平面グラフの最大彩色数を求めるものです。 [ 2 ]
二平面グラフ頂点は最大でエッジ数（平面グラフが持つことができるエッジ数の2倍）から、次数和の公式により、最大11個の隣接頂点を持つ頂点が少なくとも1つ存在することがわかります。この頂点を削除し、残りのグラフを再帰的に彩色し、削除した頂点に未使用の最小番号の色を使用すると、最大12色の彩色が得られます。これは、グラフの退化順序に対する貪欲彩色です。したがって、二平面グラフは最大12色を必要とします。[ 2 ]
9 色を必要とする二平面グラフの例は、6 頂点の完全グラフと 5 頂点のサイクル グラフの結合として構築できます。これは、これら 2 つの部分グラフが、一方の部分グラフから他方の部分グラフへのすべての可能なエッジで接続されていることを意味します。結果として得られるグラフは 11 個の頂点を持ち、完全部分グラフには 6 色、サイクル部分グラフには 3 色が必要で、合計 9 色になります。[ 2 ] 1974 年に Thom Sulanke によって構築されたこの構成は、8 色で常に十分であるという Ringel の予想を否定しました。[ 6 ]その後、9 色を必要とする最小グラフである二平面9 臨界グラフの無限族が構築されました。[ 8 ] [ 9 ]
この問題に関してそれ以上の進展が見られないにもかかわらず、2018年にエレン・ゲスナーは、この問題の正しい色の数は11であると推測した。彼女は、10色二平面グラフの候補として、グラフなどをいくつか提案している。サイクルグラフとクリークの強積として得られるグラフ、および任意の頂点を取り除いて得られるグラフこれらのグラフは、より少ない色数で彩色した場合に最大の色クラスとなるほど大きな独立集合を持たないため、10 色が必要であることが示されています。さらに、これらは二平面グラフが持つことができるエッジ数の制限を満たしています。しかし、これらを二平面グラフ (または地球-月面図) として表現することは依然として困難です。[ 10 ] 2023 年に、後者のグラフは二平面ではないことが確認されました。[ 11 ]
二平面グラフの着色の応用例の1つは、プリント基板の短絡テストです。これらの基板内の電気導体には交差がありますが、（両面プリント基板の場合）それらの隣接関係は二平面グラフを形成すると仮定できます。このグラフに色を付けた後、同じ色の導体をすべて互いに接続する追加回路を追加し、異なる色のペア間の接続をテストすることで、隣接する導体間の短絡を検出できます。注意すれば、このアイデアを使用して、回路ごとに必要なテストの数をわずか4つに減らすことができます。[ 2 ] [ 12 ]
この問題のさまざまな一般化も検討されており、2つ以上の惑星を持つ問題や、惑星ごとに複数の地域を持つことができる国を持つ問題のバージョンなどが含まれる。[ 13 ] [ 14 ] 1つの惑星と国ごとに複数の地域を持つ地図は、ヒーウッドの帝国問題となる。[ 2 ] [ 7 ] 2つ以上の惑星を持つが、惑星ごとに1つの地域しかない地図は、厚さが惑星の数以下であるグラフに対応する。これらのグラフについては、より正確な（ただしまだ不完全な）結果が知られている。厚さのグラフについては、および対応する-惑星マップでは、彩色数は最大で地球・月問題で使用されたのと同じ縮退論法によって。また、完全なグラフ頂点には厚みがあるこれらのグラフの一部を表示するには色。したがって、この場合、上限と下限は互いに2色以内の差になります。[ 15 ]
