平面グラフ判定

平面グラフ判定

平面グラフ判定電卓は、単純無向グラフが平面（2つのエッジが交差することなく平面上に描画可能）であるかどうかを判定します。グラフがテストに合格しなかった場合は、クラトフスキの証明（K₅（5頂点の完全グラフ）または K₃,₃（3+3頂点の完全二部グラフ）のいずれかの細分）を見つけて視覚化します。このツールは、教育、競技プログラミングのウォーミングアップ、および小規模なグラフ構成の迅速な整合性チェックのために構築されています。

「平面」とはどういう意味ですか？

グラフ G = (V, E) が平面であるとは、エッジが共有する端点でのみ交わるように、平面に埋め込む（描画する）ことができることを意味します。同様に、G は交差することなく球の表面に描画できます。平面性は純粋にトポロジー的な性質です。グラフをどのように描画するかには依存せず、交差のない描画が存在するかどうかにのみ依存します。

平面グラフは、道路や公共インフラのネットワーク、プリント基板のルーティング、正多面体のエッジグラフ、多面体の面構造など、あらゆる場所に現れます。しかし、多くの「自然な」グラフは頑固に非平面です。3つの家を交差させることなく3つのライフライン（電気・ガス・水道）に接続しようとすると、必ず K₃,₃ の壁に突き当たります。

クラトフスキの定理 — チェッカーの核心

カジミェシュ・クラトフスキは1930年に、平面性が純粋に組合せ論的な特徴付けを持つことを証明しました。

グラフ H の細分は、H のいくつかのエッジを、内部頂点がすべて新しい次数2の頂点であるより長いパスに置き換えることによって得られます。したがって、クラトフスキの定理は、K₅ と K₃,₃ が平面性に対する唯一の障害であることを示しています。すべての非平面グラフは、これらのいずれかを「引き伸ばされた」形で含んでいます。

禁止されたグラフ

オイラーの公式と高速な必要条件

（比較的コストのかかる）細分探索を実行する前に、チェッカーはオイラーの公式から導出された2つの高速な必要条件を適用します。平面上に描かれた V 個の頂点、E 個のエッジ、および F 個の面（無界の外側の面を含む）を持つ任意の連結平面グラフについて、次が成り立ちます。

単純平面グラフのすべての面は、その境界に少なくとも3本のエッジを持つという観察と組み合わせると、エッジの上限が得られます。

これらの不等式に違反するグラフは直ちに非平面であり、細分探索は必要ありません。K₅ は m = 10, n = 5 ⇒ 3n − 6 = 9 なので 10 > 9 となり、境界に違反します。K₃,₃ は m = 9, n = 6 ⇒ 2n − 4 = 8 なので 9 > 8 となり、二部グラフの境界に違反します。

細分探索の仕組み

低コストのオイラーチェックの後、チェッカーは直接細分を探索します。

1. クイックウィン — 文字通りの部分グラフとして K₅ または K₃,₃ を検出。 5つの頂点がペアごとに隣接している場合、それはそのまま K₅ です。6つの頂点が 3 + 3 に分かれ、9つの交差エッジがすべて存在する場合、それは K₃,₃ です。
2. K₅ 細分探索。 5つの「分岐」頂点（Gで次数 ≥ 4 のもの）の各候補セットについて、10個のパス（分岐のペアごとに1つ）を見つけようとします。これらのパスは内部で頂点が互いに素（分岐以外の頂点が複数のパスに現れない）であり、他の分岐を内部頂点として使用しないものである必要があります。見つかれば非平面であることが証明されます。
3. K₃,₃ 細分探索。 6つの分岐（次数 ≥ 3）と 3 + 3 の二部分割を選択します。同じ内部頂点が互いに素という条件で、9つのクロスパスを探索します。
4. 証明が見つからない ⇒ 平面。 サイズ制限内でどちらの細分も見つからない場合、クラトフスキの定理により、そのグラフが平面であることが保証されます。

頂点が互いに素なパスを見つけることは一般にNP困難であるため、チェッカーは有界ランダム化強欲探索を使用します。各反復で必要なペアを難易度順に並べ替え、ランダム化されたBFSを使用して最も難しいペアのパスを最初に選択し、それらの内部頂点を除去して続行します。その特定の順序が失敗した場合は、順序をシャッフルして最大40回再試行します。テストされたすべての小規模グラフ（最大16頂点）において、これは証明が存在する場合にはそれを見つけるのに十分です。

この電卓の使い方

1. 上部のタブを使用して、入力形式を選択します（エッジリストまたは隣接リスト）。どちらも同じグラフをエンコードします。
2. グラフを入力します。グラフは無向として扱われるため、A-B と B-A は同じエッジです。
3. 「平面性を判定」をクリックします。ツールは判定結果を報告し、段階的な推論（オイラー、二部グラフ、クラトフスキ）を表示し、グラフをレンダリングします。
4. 非平面グラフの場合、視覚化によって K₅ または K₃,₃ の細分が色付けされ、10個（または9個）の頂点が互いに素なパスがリストされます。パスの行をクリックすると、そのパスのみを抽出して表示できます。
5. 平面グラフの場合、グラフ構造とともに面の数 F = m − n + 1 + c が報告されます。

実行例 1 — K₄ は平面

K₄ は n = 4, m = 6 です。4頂点以下のすべてのグラフは平面であり、実際に K₄ は三角形の中に1つの頂点があり、それが3つの角すべてに接続されている形として埋め込むことができます。オイラーによれば、F = 6 − 4 + 2 = 4 つの面（3つの三角形の内側の面と1つの外側の面）があります。

実行例 2 — K₃,₃ は非平面

K₃,₃ は n = 6, m = 9 です。これは二部グラフであるため、二部グラフの境界が適用されます：m = 9 > 2n − 4 = 8。これだけで非平面性が証明されます。証明は自明です。K₃,₃ それ自体が禁止された部分グラフだからです。ツールは 3 + 3 の分割と 9 つの直接エッジを強調表示します。

実行例 3 — ピーターセングラフ

ピーターセングラフは n = 10, m = 15 なので、m ≤ 3n − 6 = 24 となり、高速なオイラーチェックを通過します。しかし、これは非平面であることで有名です。チェッカーは K₃,₃ の細分を見つけ出します。外側の五角形と内側の五芒星から6つの頂点を選び、残りの4つの頂点を通る互いに素なパスによってすべてのクロスペアをルーティングできることを示します。ツールはこの証明を描画し、1930年代の幾何学を具体化します。

平面性の応用

• VLSI および PCB ルーティング。 単層回路は、接続グラフが平面である場合にのみ実現可能です。非平面のネットは、ビアや追加の層を必要とします。
• グラフ描画と視覚化。 平面グラフは、交差のない明確なレイアウトが可能です。これは、路線図、コールグラフ、回路図などに役立ちます。
• アルゴリズム設計。 多くのNP困難問題（最大カット、頂点被覆、グラフ同型性）は、平面グラフに限定されると多項式時間で解けるようになります。
• グラフ彩色。 四色定理は、すべての平面グラフが4色で彩色可能であることを保証します。これは平面性に依存する古典的な結果です。
• 組合せ最適化。 平面最短経路、最大流、最小カットにはすべて、専用の高速アルゴリズムが存在します。
• 分子化学。 ベンゼン環などの芳香族炭化水素のグラフは平面ですが、特定の籠型分子はそうではありません。

よくある質問

グラフにおける「平面」とはどういう意味ですか？

グラフが平面であるとは、共有頂点以外でエッジが互いに交差しないように平面上に描画できることを意味します。同様に、交差することなく球の表面に描画できる場合、そのグラフは平面です。木、閉路、立方体グラフ、正多面体はすべて平面ですが、K₅ と K₃,₃ は代表的な非平面グラフの例です。

クラトフスキの定理とは何ですか？

クラトフスキの定理は、有限グラフが平面であるための必要十分条件は、K₅ または K₃,₃ の細分である部分グラフを含まないことであると述べています。細分は、いくつかのエッジをより長いパス（新しい次数2の頂点を介したもの）に置き換えることで得られます。これにより、非平面性の具体的な組合せ論的証明が得られます。

K₅ と K₃,₃ の違いは何ですか？

K₅ は5つの頂点を持ち、すべてのペアがエッジで結ばれており、合計10本のエッジがあります。K₃,₃ は6つの頂点を持ち、3つずつの2つのグループに分けられ、グループ間のすべてのペアが結ばれており、合計9本のエッジがあります。どちらも最小の非平面グラフであり、平面性の禁止マイナーを形成します。

オイラーの不等式はどのように役立ちますか？

平面連結グラフのオイラーの公式 V − E + F = 2 と、単純平面グラフの面は少なくとも3本のエッジを持つという事実から、m ≤ 3n − 6 が得られます。これに違反する単純グラフは直ちに非平面です。二部平面グラフの場合は面が少なくとも4本のエッジを持つため、より厳しい m ≤ 2n − 4 が適用されます。チェッカーはこれらを高速な判定ルールとして使用します。

サイズ制限はありますか？

このチェッカーは最大16頂点、60エッジまで対応しています。これは、ピーターセングラフ、メビウス・カントールグラフ、小さな超立方体、完全グラフ K₇ など、典型的な教育用グラフをカバーしています。より大きなグラフには、Hopcroft-Tarjan などの線形時間専用アルゴリズムが必要です。

証明となる細分はどのように描画されますか？

グラフが非平面の場合、見つかった K₅ の5つの分岐頂点（または2つのトリプルAとBに分けられた K₃,₃ の6つの分岐頂点）が内側のリング上に強調表示されます。必要な10個（または9個）の内部で頂点が互いに素なパスは、それぞれ異なる色で描画され、K₅ または K₃,₃ のトポロジーを視覚的に追跡できます。細分に関係のない頂点やエッジは薄く表示されます。

参考文献

• 平面グラフ — Wikipedia
• クラトフスキの定理 — Wikipedia
• オイラー標数 — Wikipedia
• ピーターセングラフ — Wikipedia
• Wagner's theorem (minor version) — Wikipedia