組合せとグラフの理論(塩田)第2回 (1) 無向グラフ

グラフの表し方

 もののつながり方に向きを考えないグラフを「無向グラフ」と呼びます。 無向グラフ $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\,\}$ と合わせて絵を復活させることができますね。
Ex.1 頂点集合が $V=\{\,1,2,3\,\}$, 辺集合が $E=\{\,12,23\,\}$ であるグラフを描け。

その他の用語

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

     ややこしいようですが、「隣」は同じもの同士に使う言葉、と覚えると良いでしょう。