第2回グラフの基礎概念と例のソースを表示

== 概要 ==
グラフの基礎概念<br>
* グラフの同形
*: グラフG1とG2が同形である。 ⇔ G1とG2の点の間に1対1対応があり、G1の任意の2点を結ぶ辺数がG2の対応する2点を結ぶ辺数に等しい。
* 次数と握手補題
*: 次数 : 点に接続している辺の本数である。
*: 握手補題 : 任意のグラフのすべての点の次数を合計すれば偶数になる。
* 行列を用いたグラフの表現法
*# 隣接行列 : 点iとjを結ぶ辺の本数をij要素とする行列。
*# 接続行列 : 点iが辺jに接続しているときij要素が1、接続していないとき0であるような行列。
<br>
グラフの例<br>
* 完全グラフ : 相異なる2つの点がすべて隣接している単純グラフ。n個の点をもつ完全グラフをK<sub>n</sub>と表す。<br>K<sub>n</sub>には、<math>\frac{n(n - 1)}{2}</math>本の辺がある。
* 正則グラフ : どの点の次数も同じであるグラフ。次数がrであるとき、r-正則グラフと呼ばれる。
*: ピーターセングラフ
*: プラトングラフ
* 2部グラフ : グラフGの点集合を、互いに同じ要素を持たない集合AとBに分割し、Gの全ての辺はAの点とBの点を結ぶようにしたグラフ。
*: 完全2部グラフ
*: k-立方体
<br><br>

== 単純グラフ ==
単純グラフ(simple graph)は、<math>G = (V(G), E(G))</math>で表される。<br>
<br>
V(G)は、点、頂点または節点と呼ばれる元からなる空でない有限集合である。<br>
E(G)は、辺と呼ばれる元からなる有限集合である。辺はV(G)の異なる2点の非順序対である。<br>
<br>
V(G)はGの点集合と呼ばれ、E(G)はGの辺集合と呼ばれる。<br>
辺{v, w}は、点vと点wを結ぶと言い、vwと略記される。<br>
<br>
例<br>
下図は単純グラフGを表す。<br>
* Gの点集合V(G) = {u, v, w, z}
* Gの辺集合E(G) = {uv, uw, vw, wz}
<br><br>

== 一般グラフ ==
単純グラフにおいて、以下の2つを考慮したグラフを一般グラフ(general graph)あるいは単にグラフという。<br>
* 2つの点を結ぶ辺が2本以上であることを許す。
* どの辺も2つの相異なる点を結ぶという制約を外し、同じ点を結ぶ辺(ループ)の存在を許す。
<br>
一般グラフの定義<br>
一般グラフGは、点と呼ばれる元からなる空でない有限集合V(G)と、<br>
辺と呼ばれるV(G)の(必ずしも相異なるとは限らない)元の非順序対からなる有限な多重集合であるE(G)からなる。<br>
<br>
V(G)をGの点集合、E(G)を辺多重集合と呼ぶ。<br>
多重集合とは、同じ元が複数個あることを認める集合のことである。{a, a, a, b, c, c}<br>
<br>
下図は、一般グラフGを表す。<br>
V(G) = {u, v, w, z}<br>
E(G) = {vv, vv, vw, vw, vw, uw, uw, wz}<br>

<br><br>

== 同形(同型) ==
2つのグラフG1とG2の点の間に1対1対応があり、G1の任意の2点を結ぶ辺数がG2の対応する2点を結ぶ辺数に等しいとき、<br>
G1とG2は同形(isomorphic)であるという。<br>
<br>
グラフが同形か否かを調べるためには、2つのグラフの各点にラベルを付けて、<br>
それら2つのグラフ間の各点のラベルの対応を調べる。<br>
<br>
例<br>
下図の2つのグラフは同形である。<br>
点の対応 : u ⇔ l、v ⇔ m、w ⇔ n、x ⇔ p、y ⇔ q、z ⇔ r<br>
<br>
同形の判定法<br>
* グラフGとHが同形であることを示す方法
*: Hの点の名前を付け替えるとGになる。
*: Hの点のいくつかを移動するとGと同じ形になる。
* グラフGとHが同形でないことを示す方法
*: Gの点の名前をどのように変えてもHにならないことを示す。名前の付け方をすべて試す必要があり、難しい。
*: 2つのグラフの特徴を見て、異なる特徴を挙げる。
* グラフ間における異なる特徴の例
*: 点の数や辺の数が違えば同形ではない。
*: 点と辺の数がそれぞれ同じでも、次数列が異なれば同形ではない。次数列については後述する。
*: 点のつながり方が違えば同形ではない。
*: 一方に長さkのサイクルがあり、他方になければ同形ではない。
<br><br>

== グラフの和 ==
2つのグラフG1 = (V(G1), E(G1)), G2 = (V(G2), E(G2))を考える。<br>
ここで、V(G1)とV(G2)は共通の要素を持たないとする。<br>
このとき、G1とG2の和G1∪G2 = (V(G1∪G2), E(G1∪G2))は、点集合V(G1)∪V(G2)と辺集合E(G1)∪E(G2)を持つグラフである。<br>
<br>
例<br>
グラフG1とG2の和G1∪G2<br>

<br><br>

== 連結・非連結グラフ ==
2つのグラフの和として表現できないグラフは、連結と呼ばれる。<br>
2つのグラフの和として表現できるグラフは非連結と呼ばれる。<br>
<br>
連結なグラフを連結グラフという。<br>
非連結なグラフを非連結グラフという。<br>
<br>
任意の非連結グラフGは連結グラフの和として表せる。このとき、各々の連結グラフはGの成分と呼ばれる。<br>
<br>
例<br>
3つの成分G1、G2、G3からなる非連結グラフG<br>

<br><br>

== 隣接 ==
* 点の隣接
*: グラフGに2つの点vとwを結ぶ辺vwがあるとき、vとwは隣接しているという。
*: このとき、点vとwは辺vwに接続しているという。
* 辺の隣接
*: 同様に、グラフGの2本の辺が1つの点を共有しているとき、その2辺は隣接しているという。
<br>
例<br>
下図に、隣接している点v、wと隣接している辺e、fを示す。<br>

<br><br>

== 単純グラフの表現法 ==
単純グラフの別な表現法として以下の2つがある。<br>
* 表現法1
*: 隣接点をリストする方法。グラフの各点に隣接している点をリストにする。
* 表現法2
*: 行列を使用する方法。隣接行列と接続行列を使用する。
<br>
単純グラフGの隣接点をリストする方法<br>

<br>
隣接行列と接続行列を使用する方法<br>
* 隣接行列
*: 単純グラフGの点が{1, 2, ..., n}とラベル付けされているとき、
*: 単純グラフGの隣接行列Aとは、点iとjを結ぶ辺の本数をij要素とするn×n行列である。
* 接続行列
*: 単純グラフGについて、更に、辺が{1, 2, ..., m}とラベル付けされているとき、
*: 単純グラフGの接続行列Mとは、点iが辺jに接続しているときij要素が1であり、接続していないとき0であるようなn×m行列である。

<br><br>

== 次数と次数列 ==
グラフGの点vの次数は、vに接続している辺の本数である。点vの次数はdeg(v)で表す。<br>
グラフの各点の次数を増加順に、必要ならば同じ次数を繰り返し表したものを、グラフの次数列という。<br>
<br>
次数を計算するときには、vの1つのループは2本として計算する。<br>
次数0の点は孤立点と呼ばれ、次数1の点は端点と呼ばれる。<br>
<br>
例<br>
下図のグラフには、端点が1個、次数3の点が1個、次数6の点が1個、次数8の点が1個ある。<br>
下図のグラフの次数列は、(1, 3, 6, 8)である。<br>
<br><br>

__FORCETOC__
[[カテゴリ:グラフ理論]]