導入
グラフ理論では、平面グラフとは、他のエッジと交差するエッジ (または有向グラフの場合は円弧) のない平面上で表現できるという特性を持つグラフです。言い換えれば、これらのグラフはまさに計画に没入できるグラフです。
これらのグラフに関連付けられたメソッドを使用すると、スリー ハウス パズルや、 4 色の定理などのより難しい問題の解決が可能になります。
例と反例
1) 2) 3) 4)
- 2 つのエッジの間に交差がないため、このグラフは明らかに平面です。
- これは 4 つの頂点 (K) を持つ完全なグラフです。それは平面です。三角形1 2 3の頂点4 を移動すると、エッジの交差がなくなっていることがわかります。
- 頂点 (K) が 5 つある完全なグラフです。平面的ではありません。
- これは 6 つの頂点を持つ完全な 2 部グラフであり、そのうちの 3 つは他の 3 つ (K) に接続されています。平面的ではありません。
実際、K と K は最小の非平面グラフであり、これは以下の特性説明からわかります。
プロパティ
この段落の残りの部分では、 G は平面グラフ、 n はノードの数、 aはエッジ (またはリンク) の数、 f は面の数を示します。面は、平面内のグラフの補体の連結コンポーネントです。面Fの次数はその境界サイクルの長さであり、その終点と結合する起点の可能な最短パスを考慮し、エッジの数 (その多重度を含む) が面Fの次数になります。それはdeg (F)で表されます。最初のほぼ明白な式が得られます。
実際、サイクルの各要素エッジは 2 つの面に隣接し、どのサイクルにも共有されていないエッジは、グラフの補数の非境界コンポーネントの境界パスによって 2 回横断されます。
接続された平面グラフのオイラーの公式は次のとおりです。
これを実証する簡単な方法は、サイクルのないグラフ (片側) に対してそれを確立し、帰納法によってサイクルを生成するエッジを追加することです。この公式により、少なくとも 3 つの頂点を持つ単純な接続された平面グラフが次の限界を満たすことを証明できます。
単純なグラフとは、ループがなく (ループとは同じ始点と終点を持つエッジです)、複数のエッジがないグラフです (複数のエッジは同じ始点と同じ終点を持つエッジです)。この公式は単純に示されており、グラフには少なくとも 3 つのノードがあり単純であるため、すべての面は少なくとも 3 に等しい次数を持ちます。式(1)から、3. f は2. a以下であると推定されます。オイラーの公式により結論が得られます。
この増加は、 K 5が平面ではないという事実の証明の根源となります。実際、 K 5には 10 個のエッジと 5 個のノードがあり、この結果は増加(2)と互換性がありません。増加の仮説(2)で、グラフに三角形がない場合、増加は次のようになります。
推論は同じですが、今回は面の次数が少なくとも 4 に等しいため、 K 3.3 は平面ではないことが推測されます。詳しくは『三家の謎』の記事に記載しています。
最初の補題は役に立ちます。
- 接続された平面グラフは、同じノードを持つ接続されたツリーにエッジを追加することで取得できます。
ツリーは、面を 1 つだけ含むグラフです。グラフの面の数を帰納法で計算します。
グラフに面が 1 つだけあり、グラフがツリーであり、命題が自明に検証されると仮定します。この命題がfに対して真であると仮定し、 f + 1 面を持つグラフGに対してそれを示します。ジョルダンの定理は、複数の面がある場合、エッジによって形成されるジョルダン曲線が存在することを示しています。グラフGの曲線のエッジAの 1 つを差し引くと、以前は 2 つの面を形成していたグラフの補部分の右側と左側の部分が 1 つになり、ジョルダン曲線の残りはGが常に接続されていることを保証します。 Aの切断されたグラフは再発仮説を検証し、接続されたツリーにエッジを追加することによって取得されます。最後のエッジAを追加すると、最初のグラフが得られます。
- オイラーの公式:
まず、ノード数nに関する帰納法によって、ツリーについての命題を証明しましょう。ツリーにノードが 1 つしか含まれておらず、面がありエッジが存在しない場合、式は検証されます。この式がnに当てはまると仮定して、 n + 1 個のノードを含むツリーGについてそれを示してみましょう。ツリーには 1 つの面しか含まれないため、単一のエッジに接続された少なくとも 1 つのノードNが含まれます (そうでない場合、ジョルダンの定理により少なくとも 2 つの面の存在が保証されます)。このノードと隣接エッジから削除された木G は、 n 個のノードを含む接続された木であり、漸化仮説が検証されます。ノードNと関連するエッジの追加は、ノードとエッジの追加に対応し、オイラーの公式はGに対して当てはまり、これでこの最初のステップが完了します。
ここで、面の数に関する帰納法によって接続グラフの命題を証明しましょう。 fが 1 に等しい場合、式は前の反復に従って検証されます。 f 個の面を持つ任意のツリーに対する真の値を仮定し、それをf + 1 個の面を持つグラフGに対して示してみましょう。補助定理の再帰は、新しいグラフがまだ接続されており、正確にf 個の面を持つようにGからエッジを減算できることを示しています。次に、オイラーの公式は漸化仮説によって検証されます。欠落しているエッジを追加してもノードの数は変わりませんが、エッジと面の数は 1 つずつ増えます。オイラーの公式が再度検証され、デモンストレーションが完了します。