📂グラフ理論

数学におけるグラフとネットワーク

定義¹

1. 頂点とそれらを結ぶ線から成る集合をグラフまたはネットワークと呼ぶ。頂点の集合を$V$、線の集合を$E$としよう。
2. $V(G) := V$の要素を$G$の ヴァーテックス^vertexまたは ノード^nodeと呼ぶ。
3. $E(G) := E$の要素を$G$の エッジ^edgeまたは リンク^linkと呼ぶ。
4. 自分自身に繋がるエッジをループ^loopと呼ぶ。
5. 二つのヴァーテックスがエッジで繋がっている場合、隣接している^adjacentと言う。
6. エッジに向きがあるグラフを有向グラフ^digraphと言う。
7. 有限なヴァーテックスを持ち、二つのヴァーテックスを結ぶエッジが一つだけで、ループが存在せず、有向グラフでないグラフを単純グラフ^{simple graph}と言う。

説明

必ずしもそうではないが、同じ概念であっても純粋数学ではグラフという言葉を好んで用い、応用数学ではネットワークという言葉を好んで用いる傾向がある。ただし、どちらかと言えば、同義語があり、それぞれの分野ではかなりの影響力を持っているので、混在して使うことはあまりない。

1. 一般的に言うグラフとは、上の図のように自由な形をしている。
2. 黒い丸はそれぞれのヴァーテックスを意味し、位置の概念は持たない。純粋なグラフ理論では、グラフのオーダー^orderは通常、このヴァーテックス集合の基数 $n = |V(G)|$を指す。上のグラフのオーダーは$5$である。
3. ヴァーテックスを結ぶエッジも同様に、その関係のみを表すもので、形や長さの概念はない。ちなみに、エッジは通常、韓国人が直感的に思うように[エッヂ]ではなく[エッジ]と発音されるのが正しい。純粋なグラフ理論では、グラフのサイズ^sizeは通常、このエッジ集合の基数$m = |E(G)|$を指す。上のグラフのサイズは$8$である。しかし、応用ネットワーク理論では、サイズは単にグラフのオーダー$|V(G)|$を呼ぶことが多い。これは分野による文脈で区別する必要がある。
4. 左上のヴァーテックスは自分自身に繋がるエッジを持ち、このためにループと呼ばれる。
5. 二つのヴァーテックスが隣接しているとは、エッジで繋がっているということを意味し、再び、その関係のみが重要であり、目に見える距離は重要ではない。二つのヴァーテックス$u, v$が隣接している場合、$u \sim v$のように表され、グラフ$G$でヴァーテックス$v \in V(G)$に隣接するヴァーテックスを集めた集合を$v$のネイバーフッド$N_{G} (v)$のように表現することもある。
6. 有向グラフとは、上の図のようにエッジに方向性があるグラフを言う。有向グラフでは、エッジはアーク^arcとも呼ばれる。ヴァーテックス$u$から$v$へ入るエッジは$u \to v$と表記され、$u$をテイル^tail、$v$をヘッド^headと呼ぶ。
7. 単純グラフという言葉は難しそうだが、簡単に言えば、ループやマルチエッジ、ディレクションなどがなく、上の図のようなきれいなグラフを指す。一般に、グラフ理論と言えば、このような単純な形に興味を持つのが普通である。

難しい定義

これらの定義は、グラフの概念を簡単に説明するが、厳密さにはいくらか問題がある。したがって、以下のより複雑な定義を紹介する。概念は文字通り上で簡単に定義されたものと同じなので、数学的な表現に慣れていれば理解するのに大きな困難はないだろう。

1. 集合 $V \ne \emptyset$ と 二項関係 $\sim \subset V^2$ について$G := \left( V, \sim \right)$をグラフまたはネットワークと呼ぶ。
2. $V(G) := V$の要素を$G$のヴァーテックスまたは ノードと呼ぶ。
3. $E(G) := \sim$の要素を$G$のエッジまたは リンクと呼ぶ。
4. $v \in V(G)$に対して$(v,v) \in E(G)$をループと呼ぶ。
5. $v_{1} , v_{2} \in V(G)$について$(v_{1} , v_{2} ) \in E(G)$であれば$v_{1}$と$v_{2}$が隣接していると言う。
6. $\sim$が対称関係でなければ有向グラフ^digraphと呼ぶ。
7. 有限集合$V$に対し、対称関係$\sim \subset \left\{ (v_{1} , v_{2} ) \in V^2 \mid v_{1} \ne v_{2} \right\}$をエッジとして、二つのヴァーテックスを結ぶエッジが一つだけのグラフを単純グラフと呼ぶ。