13,230
回編集
→一般グラフ
(→グラフの和) |
(→一般グラフ) |
||
| (同じ利用者による、間の10版が非表示) | |||
| 52行目: | 52行目: | ||
* <math>V(G) = \{u, v, w, z\}</math> | * <math>V(G) = \{u, v, w, z\}</math> | ||
* <math>\{vv, vv, vw, vw, vw, uw, uw, wz\}</math> | * <math>\{vv, vv, vw, vw, vw, uw, uw, wz\}</math> | ||
[[ファイル:Graph Theory 2 | [[ファイル:Graph Theory 2 18.jpg|フレームなし|中央]] | ||
<br><br> | <br><br> | ||
| 102行目: | 102行目: | ||
<br> | <br> | ||
例<br> | 例<br> | ||
下図に、3つの成分G<sub>1</sub>、G<sub>2</sub>、G<sub>3</sub>からなる非連結グラフGを示す。<br> | |||
[[ファイル:Graph Theory 2 4.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
| 114行目: | 114行目: | ||
<br> | <br> | ||
例<br> | 例<br> | ||
下図に、単純グラフGの隣接点をリストする方法を示す。<br> | |||
隣接している点v、wと隣接している辺e、fを示す。<br> | |||
[[ファイル:Graph Theory 2 5.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
| 122行目: | 123行目: | ||
* 表現法1 | * 表現法1 | ||
*: 隣接点をリストする方法。グラフの各点に隣接している点をリストにする。 | *: 隣接点をリストする方法。グラフの各点に隣接している点をリストにする。 | ||
*: <br> | |||
*: 下図に、単純グラフGの隣接点をリストする方法を示す。 | |||
[[ファイル:Graph Theory 2 6.jpg|フレームなし|中央]] | |||
* 表現法2 | * 表現法2 | ||
*: 行列を使用する方法。隣接行列と接続行列を使用する。 | *: 行列を使用する方法。隣接行列と接続行列を使用する。 | ||
*: <br> | |||
*: 下図に、隣接行列を使用する方法を示す。 | |||
* | |||
*: 単純グラフGの点が{1, 2, ..., n}とラベル付けされているとき、 | *: 単純グラフGの点が{1, 2, ..., n}とラベル付けされているとき、 | ||
*: 単純グラフGの隣接行列Aとは、点iとjを結ぶ辺の本数をij要素とするn×n行列である。 | *: 単純グラフGの隣接行列Aとは、点iとjを結ぶ辺の本数をij要素とするn×n行列である。 | ||
* | *: <br> | ||
*: 下図に、接続行列を使用する方法を示す。 | |||
*: 単純グラフGについて、更に、辺が{1, 2, ..., m}とラベル付けされているとき、 | *: 単純グラフGについて、更に、辺が{1, 2, ..., m}とラベル付けされているとき、 | ||
*: 単純グラフGの接続行列Mとは、点iが辺jに接続しているときij要素が1であり、接続していないとき0であるようなn×m行列である。 | *: 単純グラフGの接続行列Mとは、点iが辺jに接続しているときij要素が1であり、接続していないとき0であるようなn×m行列である。 | ||
[[ファイル:Graph Theory 2 7.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
| 148行目: | 149行目: | ||
下図のグラフには、端点が1個、次数3の点が1個、次数6の点が1個、次数8の点が1個ある。<br> | 下図のグラフには、端点が1個、次数3の点が1個、次数6の点が1個、次数8の点が1個ある。<br> | ||
下図のグラフの次数列は、(1, 3, 6, 8)である。<br> | 下図のグラフの次数列は、(1, 3, 6, 8)である。<br> | ||
[[ファイル:Graph Theory 2 8.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 握手補題 == | |||
補題 : 任意のグラフのすべての点の次数を合計すれば偶数になる。<br> | |||
グラフの各辺は2本あるので、全ての点の合計は辺数の2倍である。<br> | |||
<br><br> | |||
== 部分グラフ == | |||
部分グラフ(sub graph)とは、その点はすべてV(G)に属し、その辺はすべてE(G)に属すグラフのことである。<br> | |||
グラフの辺と点を除去して部分グラフを作ることができる。<br> | |||
<br> | |||
例<br> | |||
下図Aのグラフは、下図Bのグラフの部分グラフである。<br> | |||
下図Aのグラフは、下図Cのグラフの部分グラフではない。下図Cのグラフには、点と辺により作られる三角形が含まれないため。<br> | |||
[[ファイル:Graph Theory 2 9.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 辺と点の除去 == | |||
* 辺の除去(1) | |||
*: eがグラフGの辺であるとき、Gから辺eを除去して得られるグラフをG - eと書く。 | |||
* 辺の除去(2) | |||
*: グラフGの辺の集合の部分集合をFとしたとき、GからFの辺をすべて除去して得られるグラフをG - Fと書く。 | |||
* 点と辺の除去(1) | |||
*: 同様にして、グラフGから点vおよびvに接続する辺すべてを除去して得られるグラフをG - vと書く。 | |||
* 点と辺の除去(2) | |||
*: SがGの点の集合の部分集合であるとき、Sの点とそれらに接続している全ての辺を除去して得られるグラフをG - Sと書く。 | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 10.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 辺の縮約 == | |||
グラフGから、辺eを除去し、その端点vとwを同一視して1点にすることを、グラフGの辺eに対する縮約(contraction)という。<br> | |||
即ち、端点vまたはwに接続していた(辺e以外)の辺を新しくできた点に接続させたグラフである。<br> | |||
グラフGの辺eに対する縮約グラフを、<math>G \backslash e</math>と書く。<br> | |||
<br> | |||
例<br> | |||
下図に、グラフGの辺eに対する縮約グラフを示す。<br> | |||
[[ファイル:Graph Theory 2 11.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 空グラフ 閉路グラフ 道グラフ 車輪グラフ == | |||
* 空グラフ(Null graph) | |||
*: 辺集合が空であるグラフのことである。空グラフでは、すべての点が孤立点である。 | |||
*: m個の点の空グラフを、N<sub>n</sub>と表す。下図に、空グラフN<sub>4</sub>を示す。 | |||
* 閉路グラフ(cycle graph) | |||
*: 全ての点の次数が2の連結グラフを閉路グラフという。 | |||
*: n個の点をもつ閉路グラフを、C<sub>n</sub>と書く。 | |||
* 道グラフ(path graph) | |||
*: C<sub>n</sub>から1つの辺を除いて得られるグラフを、n個の点をもつ道グラフという。 | |||
*: n個の点をもつ道グラフを、P<sub>n</sub>と書く。 | |||
* 車輪グラフ(wheel graph) | |||
*: C<sub>n - 1</sub>に1つの新しい点vを加え、点vと他の全ての点とを辺で結んで得られるグラフを、n点の車輪グラフという。 | |||
*: n点の車輪グラフをW<sub>n</sub>と書く。 | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 12.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 完全グラフ == | |||
完全グラフ(Complete graph)とは、相異なる2つの点がすべて隣接している単純グラフのことである。<br> | |||
n個の点をもつ完全グラフをK<sub>n</sub>と表す。完全グラフK<sub>n</sub>には、<math>\frac{n(n - 1)}{2}</math>本の辺がある。<br> | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 13.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
== 正則グラフ == | |||
正則グラフ(Regular graph)とは、どの点の次数も同じであるグラフのことである。<br> | |||
次数がrであるとき、次数rの正則グラフあるいはr-正則グラフという。<br> | |||
<br> | |||
特に、彩色問題で重要となるのは、次数3の正則グラフである。このグラフは、3次(cubic)グラフともいう。<br> | |||
3次グラフの中で有名な例として、ピーターセングラフがある。<br> | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 14.jpg|フレームなし|中央]] | |||
<br> | |||
空グラフNnは次数0の正則グラフである。<br> | |||
閉路グラフCnは次数2の正則グラフである。<br> | |||
完全グラフKnは次数n - 1の正則グラフである。<br> | |||
正則グラフの一種として、プラトングラフがある。プラトングラフは正多面体(プラトンの多面体)の頂点と辺から作られたグラフである。<br> | |||
<br><br> | |||
== 2部グラフと完全2部グラフ == | |||
===== 2部グラフ ===== | |||
2部グラフとは、グラフGの点集合を、互いに同じ要素をもたない集合AとBに分割し、<br> | |||
グラフGの全ての辺は集合Aの点と集合Bの点を結ぶようにしたグラフ。<br> | |||
<br> | |||
グラフGの各点が黒の点(Aの要素)と白の点(Bの要素)を結ぶように、グラフGの点を黒と白で塗れるとき、Gは2部グラフである。<br> | |||
<br> | |||
===== 完全2部グラフ ===== | |||
完全2部グラフとは、グラフGの点集合を、互いに同じ要素をもたない集合AとBに分割したとする。<br> | |||
このとき、Aの各点がBの各点と1本の辺で結ばれている2部グラフを、完全2部グラフという。<br> | |||
<br> | |||
黒の点(Aの要素)をr個、白の点(Bの要素)をs個をもつ2部グラフをK<sub>r, s</sub>と書く。<br> | |||
2部グラフK<sub>r, s</sub>には、r + s個の点とr×s本の辺がある。<br> | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 15.jpg|フレームなし|中央]] | |||
<br><br> | |||
== k-立方体 == | |||
k-立方体(k-cube)とは、<math>a_i = 0</math>または<math>a_ = 1</math>であるような1つの列<math>(a_1, a_2, \cdots, a_k)</math>に1つの点を対応させたグラフであり、<br> | |||
1個だけ異なるa<sub>i</sub>をもつ2つの列に対応する2つの点が辺で結ばれる。<br> | |||
k-立方体を、Q<sub>k</sub>と書く。<br> | |||
Q<sub>k</sub>は、2<sup>k</sup>個の点とk2<sup>k - 1</sup>本の辺をもつ次数kの正則2部グラフである。<br> | |||
<br> | |||
立方体のグラフはQ<sub>3</sub>である。<br> | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 16.jpg|フレームなし|中央]] | |||
<br><br> | |||
== 単純グラフの補グラフ == | |||
単純グラフGの補グラフ(Complement graph)Gとは、Gと同じ点集合V(G)をもち、<br> | |||
Gの2点が隣接するのはGにおけるそれら2点が隣接していないときかつそのときに限るような単純グラフである。<br> | |||
補グラフは、相補グラフともいう。<br> | |||
<br> | |||
完全グラフの補グラフは空グラフである。<br> | |||
完全2部グラフの補グラフは2つの完全グラフの和である。<br> | |||
<br> | |||
例<br> | |||
[[ファイル:Graph Theory 2 17.jpg|フレームなし|中央]] | |||
<br><br> | |||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||