グラフ理論では、平面グラフとは、他のエッジと交差するエッジ (または有向グラフの場合は円弧) を持たずに平面上で表現できる特殊なグラフを指します。
例
1) 2) 3) 4)
- 2 つのエッジの間に交差がないため、このグラフは明らかに平面です。
- これは 4 つの頂点 (K 4 ) を持つ完全なグラフです。それは平面です。三角形1 2 3の頂点4 を移動すると、エッジの交差がなくなっていることがわかります。
- これは 5 つの頂点 (K 5 ) を持つ完全なグラフです。平面的ではありません。
- これは 6 つの頂点を持つ完全な 2 部グラフであり、そのうちの 3 つは他の 3 つの頂点 (K 3,3 ) に接続されています。平面的ではありません。
実際、K 5と K 3.3 は最小の非平面グラフであり、これは以下の特性説明からわかります。
クラトフスキーの特徴
ポーランドの数学者カジミエシュ・クラトフスキは、平面グラフの次の特徴を確立しました。
- 有限グラフは、 K 5 (頂点が 5 つあるクリーク) またはK 3.3 (頂点が 3+3 ある完全な 2 部グラフ) の拡張であるサブグラフを含まない場合に限り、平面的です。
グラフの拡張は、1 つまたは複数のエッジに 1 つまたは複数の頂点を追加した結果です (例: エッジ •——• を •—•—• に変換します)。
興味
これはチェスの古典的なナイト問題です。チェス盤の上に騎士を置きます。目標は、チェスの駒の古典的な動きを尊重して、マス目ごとに 1 回だけ、すべてのマス目を通過させることです。問題を説明するために、ここでは 3 列に 4 つの正方形からなるボードを使用します。この問題はモーション グラフで表現されます。グラフの頂点はチェス盤の正方形に対応します。円弧は可能な動きを表します。したがって、ボックス 1からボックス 8またはボックス 6に進むことができます。これは、これらがグラフの最初のボックスにリンクされているためです。
このように提示されると、問題は依然として複雑です。ただし、グラフは平面なので、より直感的な方法で表すことができます。この新しい表現から、ボックス 3から始まりボックス 10に到達する解 (緑色で描かれている) を簡単に抽出できます。
平面グラフの特性は、多くの場合、人間の脳に問題を簡単に提示できるかどうかという興味のみに役立ちます。マシンの場合、アルゴリズムが地形検索を使用せず、グラフが再編成されない場合、それは同じことになります。
