第2回 グラフの基礎概念と例
概要
グラフの基礎概念
- グラフの同形
- グラフG1とG2が同形である。 ⇔ G1とG2の点の間に1対1対応があり、G1の任意の2点を結ぶ辺数がG2の対応する2点を結ぶ辺数に等しい。
- 次数と握手補題
- 次数 : 点に接続している辺の本数である。
- 握手補題 : 任意のグラフのすべての点の次数を合計すれば偶数になる。
- 行列を用いたグラフの表現法
- 隣接行列 : 点iとjを結ぶ辺の本数をij要素とする行列。
- 接続行列 : 点iが辺jに接続しているときij要素が1、接続していないとき0であるような行列。
グラフの例
- 完全グラフ : 相異なる2つの点がすべて隣接している単純グラフ。n個の点をもつ完全グラフをKnと表す。
Knには、本の辺がある。 - 正則グラフ : どの点の次数も同じであるグラフ。次数がrであるとき、r-正則グラフと呼ばれる。
- ピーターセングラフ
- プラトングラフ
- 2部グラフ : グラフGの点集合を、互いに同じ要素を持たない集合AとBに分割し、Gの全ての辺はAの点とBの点を結ぶようにしたグラフ。
- 完全2部グラフ
- k-立方体
単純グラフ
単純グラフ(simple graph)とは、多重辺やループを含まないグラフのことである。
で表される。
V(G)は、点、頂点または節点と呼ばれる元からなる空でない有限集合である。
E(G)は、辺と呼ばれる元からなる有限集合である。辺はV(G)の異なる2点の非順序対である。
V(G)はGの点集合と呼ばれ、E(G)はGの辺集合と呼ばれる。
辺{v, w}は、点vと点wを結ぶと言い、vwと略記される。
例
下図は単純グラフGを表す。
- Gの点集合
- Gの辺集合
一般グラフ
単純グラフにおいて、以下の2つを考慮したグラフを一般グラフ(general graph)あるいは単にグラフという。
- 2つの点を結ぶ辺が2本以上であることを許す。
- どの辺も2つの相異なる点を結ぶという制約を外し、同じ点を結ぶ辺(ループ)の存在を許す。
一般グラフの定義
一般グラフGは、点と呼ばれる元からなる空でない有限集合V(G)と、
辺と呼ばれるV(G)の(必ずしも相異なるとは限らない)元の非順序対からなる有限な多重集合であるE(G)からなる。
V(G)をGの点集合、E(G)を辺多重集合と呼ぶ。
多重集合とは、同じ元が複数個あることを認める集合のことである。{a, a, a, b, c, c}
下図は、一般グラフGを表す。
同形(同型)
2つのグラフG1とG2の点の間に1対1対応があり、G1の任意の2点を結ぶ辺数がG2の対応する2点を結ぶ辺数に等しいとき、
G1とG2は同形(isomorphic)であるという。
グラフが同形か否かを調べるためには、2つのグラフの各点にラベルを付けて、
それら2つのグラフ間の各点のラベルの対応を調べる。
例
下図の2つのグラフは同形である。
点の対応 : u ⇔ l、v ⇔ m、w ⇔ n、x ⇔ p、y ⇔ q、z ⇔ r
同形の判定法
- グラフGとHが同形であることを示す方法
- Hの点の名前を付け替えるとGになる。
- Hの点のいくつかを移動するとGと同じ形になる。
- グラフGとHが同形でないことを示す方法
- Gの点の名前をどのように変えてもHにならないことを示す。名前の付け方をすべて試す必要があり、難しい。
- 2つのグラフの特徴を見て、異なる特徴を挙げる。
- グラフ間における異なる特徴の例
- 点の数や辺の数が違えば同形ではない。
- 点と辺の数がそれぞれ同じでも、次数列が異なれば同形ではない。次数列については後述する。
- 点のつながり方が違えば同形ではない。
- 一方に長さkのサイクルがあり、他方になければ同形ではない。
グラフの和
2つのグラフを考える。
ここで、V(G1)とV(G2)は共通の要素を持たないとする。
このとき、G1とG2の和は、
点集合と辺集合を持つグラフである。
例
下図に、グラフG1とG2の和を示す。
連結・非連結グラフ
2つのグラフの和として表現できないグラフは、連結と呼ばれる。
2つのグラフの和として表現できるグラフは非連結と呼ばれる。
連結なグラフを連結グラフという。
非連結なグラフを非連結グラフという。
任意の非連結グラフGは連結グラフの和として表せる。このとき、各々の連結グラフはGの成分と呼ばれる。
例
3つの成分G1、G2、G3からなる非連結グラフG
隣接
- 点の隣接
- グラフGに2つの点vとwを結ぶ辺vwがあるとき、vとwは隣接しているという。
- このとき、点vとwは辺vwに接続しているという。
- 辺の隣接
- 同様に、グラフGの2本の辺が1つの点を共有しているとき、その2辺は隣接しているという。
例
下図に、隣接している点v、wと隣接している辺e、fを示す。
単純グラフの表現法
単純グラフの別な表現法として以下の2つがある。
- 表現法1
- 隣接点をリストする方法。グラフの各点に隣接している点をリストにする。
- 表現法2
- 行列を使用する方法。隣接行列と接続行列を使用する。
単純グラフGの隣接点をリストする方法
隣接行列と接続行列を使用する方法
- 隣接行列
- 単純グラフGの点が{1, 2, ..., n}とラベル付けされているとき、
- 単純グラフGの隣接行列Aとは、点iとjを結ぶ辺の本数をij要素とするn×n行列である。
- 接続行列
- 単純グラフGについて、更に、辺が{1, 2, ..., m}とラベル付けされているとき、
- 単純グラフGの接続行列Mとは、点iが辺jに接続しているときij要素が1であり、接続していないとき0であるようなn×m行列である。
次数と次数列
グラフGの点vの次数は、vに接続している辺の本数である。点vの次数はdeg(v)で表す。
グラフの各点の次数を増加順に、必要ならば同じ次数を繰り返し表したものを、グラフの次数列という。
次数を計算するときには、vの1つのループは2本として計算する。
次数0の点は孤立点と呼ばれ、次数1の点は端点と呼ばれる。
例
下図のグラフには、端点が1個、次数3の点が1個、次数6の点が1個、次数8の点が1個ある。
下図のグラフの次数列は、(1, 3, 6, 8)である。