平面グラフチェッカー — グラフが交差なしで描けるかテスト

平面グラフチェッカー — オンラインでクラトフスキースタイルのテストの使い方

1. 1

   グラフをカンマ区切りの辺リストとして入力します（例：A-B, A-C, A-D, B-C, B-D, C-D）。

2. 2

   「計算」をクリックして必要条件をチェックし、禁止された部分グラフを検索します。

3. 3

   判定 — 「確実に非平面的」または「おそらく平面的（不確定）」 — と推論のステップを確認します。

なぜ平面グラフチェッカー — オンラインでクラトフスキースタイルのテストを使うのか？

グラフが平面的であるとは、2つの辺がどこでも交差しないように平面上に描けることです。クラトフスキーの定理は正確な特徴付けを与えます：グラフは、K₅（5頂点の完全グラフ）またはK₃,₃（3頂点の2つのグループの完全二部グラフ）の細分を含む場合、かつその場合に限り非平面的です。これらのグラフの細分やマイナーを完全に検出するには、クライアント側の計算機が即座に実行できる範囲をはるかに超えた高度なアルゴリズム（ボイヤー・マーヴォルドなど）が必要です — そのため、このツールは代わりに透明に範囲を限定したアプローチを取ります：常に必要な辺数の限界をチェックし（多くの非平面グラフを除外する迅速かつ正確な方法）、小さなグラフ（8頂点以下）についてはさらに、文字通りの部分グラフとして現れるK₅またはK₃,₃を直接検索します。どちらかを見つけることは非平面性を決定的に証明します。どちらも見つからないことは平面性の強い示唆ですが、完全な証明ではありません。この検索はこれらの禁止されたグラフの細分（辺が拡張された）コピーを検出しないためです。