戻る / 次へ

グラフの表し方

　もののつながり方に向きを考えないグラフを「無向グラフ」と呼びます。 無向グラフ $G$ は、その頂点集合 $V=V(G)$ と辺集合 $E=E(G)$ のペアとして表します： $G=(V,E)$ V は vertex の頭文字、 E は edge の頭文字です。 の場合、$V=\{\,u,v,w,x\,\}$, $E=\{\,e,f,g,h\,\}$ となります。

辺の表し方の工夫

　しかし、絵を見ずに $V=\{\,u,v,w,x\,\}$, $E=\{\,e,f,g,h\,\}$ だけ知っていても、 どの頂点が結ばれているのかはわかりません。
　そこで、辺 $e$ が頂点 $u$ と $v$ を結ぶ辺であるとき、$e=uv$ と表すことにしましょう： 上の例では $E=\{\,uv, uw, vw, wx\,\}$ となります。 こう書いてあれば $V=\{\,u,v,w,x\,\}$ と合わせて絵を復活させることができますね。

その他の用語

1. ループ
   　ひとつの点から出てその点に戻る辺を「ループ」と呼びます。記号では $e=uu$ のように書ける辺のことです。
2. 多重辺
   　ふたつの点の間に複数の辺があるとき、それらを「多重辺」と呼びます。
3. 単純グラフ
   　ループも多重辺も持たないグラフを「単純グラフ」と呼びます。
4. 有限グラフ
   　頂点も辺も有限個であるグラフを「有限グラフ」と呼びます。
5. オーダー、サイズ 　漢字は書くのに時間が掛かるので、英語を使って、
   • 頂点数（＝頂点の個数）を「オーダー」
   • 辺数（＝辺の本数）を「サイズ」
   と書くことも多いです。
6. 隣接、接続
   • 頂点と頂点が辺でつながっているとき、また、辺と辺がひとつの頂点を介してつながっているとき、それらは「隣接する」と言います。
   • つながっている頂点と辺は「接続する」と言います。
   　例えば次のグラフでは
   • $u$ の隣接点は $v$ と $w$
   • $u$ と $x$ は隣接しない
   • $e$ と $f$ は隣接する
   • $e$ と $h$ は隣接しない
   • $w$ の接続辺は $f$, $g$, $h$ の３本
   というように使います。
   
   ※　ややこしいようですが、「隣」は同じもの同士に使う言葉、と覚えると良いでしょう。

戻る / 次へ