Untitled Course平面グラフ

各家屋を下の各公益事業会社に接続するようにしてください。回線が交差することはありません。

以前のケーニヒスベルク橋のように、この問題も不可能であることをすぐに発見します。一部のグラフは、エッジが重ならないように描画できるようです（これらは__平面グラフ__と呼ばれ__ます）__ 。

完全なグラフ K5平面ではない最小のグラフです。を含むその他のグラフK5ある意味でサブグラフも平面ではありません。これもK6 、 K7 、およびすべてのより大きな完全なグラフ。

3つのユーティリティパズルのグラフは2部グラフです K3,3 。非平面グラフには、 K5またはK3,3 （またはこれら2つのグラフのサブディビジョン ）をサブグラフとして。これは_クラトフスキーの定理_と呼ばれています。

オイラーの公式

すべての平面グラフは、それらが領域の数と呼ばれる__面__内に描かれている面を分割します。

これらの数値を比較すると、エッジの数が常にことがわかります。 より大きい面の数と頂点の数を足した数です。言い換えると、 F + V = E +1。この結果は__オイラーの方程式__と呼ばれ、ケーニヒスベルク橋問題を解いた同じ数学者にちなんで名付けられました。

残念ながら、グラフは無限にあり、すべてをチェックしてオイラーの方程式が機能するかどうかを確認することはできません。代わりに、あらゆるグラフで機能する簡単な証明を見つけることができます…

任意の（有限）グラフは、1つの頂点から始めて、頂点を1つずつ追加することで作成できます。新しい頂点を追加する方法にかかわらず、オイラーの方程式は有効であることを示しました。したがって、すべてのグラフで有効です。

私たちが使用したプロセスは、 __数学的帰納法__と呼ばれます。これは、最も単純なケースから始めて、より複雑なケースを構築するときにすべてのステップで結果が保持されることを示すだけで、無限に多くのケースで結果を証明するのに非常に役立つテクニックです。

多くの平面グラフは、 多角形の面を備えた3次元形状である多面体のネットに非常によく似ています。多面体を弾性バンドで構成されていると考える場合、それらを平らな平面グラフになるまで伸ばすことを想像できます。

これは、平面グラフだけでなく、すべての多面体にもオイラーの公式を使用できることを意味します-1つの小さな違いがあります。多面体をグラフに変換すると、面の1つが消えます。多面体の一番上の面が「外側」になります。グラフの。

つまり、数を数えると__{.red}エッジ__ 、 顔__と{.green}__ 任意の_多面体の__頂点_ 、あなたはそれを見つけるでしょう_{.b.blue} F_ + V = E + 。