用語集

左側のキーワードの1つを選択…

平面グラフ

読書の時間: ~20 min
このページは自動翻訳されているため、エラーが含まれている可能性があります。翻訳のレビューをご希望の場合はご連絡ください。

ここに、グラフ理論に関連する別のパズルがあります。

小さな村には3つの家と3つのユーティリティ工場があり、水、電気、ガスを生産しています。各コースを各ユーティリティプラントに接続する必要がありますが、村のレイアウトにより、異なるパイプやケーブルを横断することはできません。

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

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

K3平面です。

K4

K5 です。

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

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

平面性

これは平面グラフですが、 ${n}頂点はスクランブルされています。エッジが重ならないように頂点を再配置します。

オイラーの公式

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

頂点

エッジ
11頂点+面

頂点

エッジ
15頂点+面

頂点

エッジ
25頂点+面

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

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

FVE
010

0 + 1  =  0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.
Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.
If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.
Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.
Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

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

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

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

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

正二十面体
20 12頂点
30エッジ

菱形二十面体
62 60頂点
120エッジ

切頂二十面体
32面(12黒、20白)
60頂点
90エッジ

Archie