Untitled Course前書き

#グラフとネットワーク

私たちは毎日、無数の接続とネットワークに囲まれています。道路と線路、電話回線、インターネット、電子回路、さらには分子結合です。友人と家族の間にさえ_ソーシャルネットワーク_があります。他に例はありますか？

円と線を使って簡単なグラフのレイアウトを描くことができます。頂点の位置とエッジの長さは関係ありません。 _どのように_頂点が相互に_接続さ_れ_ているか_だけが重要です。エッジは互いに交差することもでき、直線である必要はありません。

一部の頂点とエッジを削除することにより、既存のグラフから新しいグラフを作成できます。結果はサブグラフと呼ばれます。ここでは、グラフのいくつかの例を見ることができます。色付きのエッジと頂点がサブグラフの可能性を示しています。

グラフの次数は、グラフの頂点の数であると言います。頂点の次数は、その頂点で交わるエッジの数です。

頂点の単一のループで構成されるグラフは、 サイクルと呼ばれます。すべてのサイクルに同じ数のエッジと頂点があります頂点よりも多くのエッジ頂点より少ないエッジ 。

これらの新しい定義を備えた、グラフの魅力的な特性とアプリケーションのいくつかを見てみましょう。