有向グラフと無向グラフ

グラフは、頂点と辺の集合からなる数学的構造である。グラフは、いくつかのリンク（エッジで表される）で接続されたオブジェクト（頂点で表される）の集合を表します。数学的な表記法を用いると、グラフはGで表すことができる。G = (V, E)で、Vは頂点の集合、Eはエッジの集合である。無向グラフでは、頂点と頂点を結ぶ辺には方向性がない。有向グラフでは、頂点を結ぶ辺に方向性がある。

無向グラフ

前述したように、無向グラフとは、グラフ内の頂点を結ぶ辺に方向性がないグラフのことである。図1は、頂点V={V1, V2, V3}の集合を持つ無向グラフを表したものである。上図の辺の集合は、V = {(V1, V2), (V2, V3), (V1, V3)}と書くことができる。なお、辺には方向性がないので、辺の集合をV = {(V2, V1), (V3, V2), (V3, V1)}と書かない手はない。したがって、無向グラフの辺は、順序のあるペアではありません。これが無向グラフの大きな特徴である。無向グラフは、頂点で表されるオブジェクト間の対称的な関係を表現することができます。例えば、都市の集合を結ぶ双方向の道路網は無向グラフで表すことができる。都市をグラフの頂点で表し、都市間を結ぶ双方向の道路を辺で表すことができる。

有向グラフ

有向グラフとは、頂点と頂点を結ぶ辺に方向性があるグラフのことです。図2は、頂点V={V1,V2,V3}の集合を持つ有向グラフを表している。上図の辺の集合は、V = {(V1, V2), (V2, V3), (V1, V3)}と書くことができる。無向グラフのエッジは、順序のあるペアです。形式的には、有向グラフの辺eは順序対e = (x, y)で表すことができる。ここで、xは辺eの原点、始点または初期点と呼ばれる頂点、yは終点、終点または終点と呼ばれる頂点である。例えば、都市間を一方通行で結ぶ道路網は、無向グラフで表現することができる。都市をグラフの頂点で表し、都市間を結ぶ道路を、道路上の交通の流れを考慮した有向辺で表すことができる。

有向グラフと無向グラフの違いは何ですか？