13,007
回編集
「第2回 グラフの基礎概念と例」の版間の差分
ナビゲーションに移動
検索に移動
編集の要約なし
(→次数と次数列) |
編集の要約なし |
||
| 189行目: | 189行目: | ||
下図に、グラフGの辺eに対する縮約グラフを示す。<br> | 下図に、グラフGの辺eに対する縮約グラフを示す。<br> | ||
[[ファイル:Graph Theory 2 11.jpg|フレームなし|中央]] | [[ファイル:Graph Theory 2 11.jpg|フレームなし|中央]] | ||
<br><br> | |||
== 空グラフ == | |||
空グラフ(Null graph)とは、辺集合が空であるグラフのことである。空グラフでは、すべての点が孤立点である。<br> | |||
m個の点の空グラフを、N<sub>n</sub>と表す。<br> | |||
例 | |||
下図に、空グラフN<sub>4</sub>を示す。 | |||
<br><br> | |||
== 閉路グラフ 道グラフ 車輪グラフ == | |||
* 閉路グラフ(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> | |||
<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> | |||
<br><br> | |||
== 正則グラフ == | |||
正則グラフ(Regular graph)とは、どの点の次数も同じであるグラフのことである。<br> | |||
次数がrであるとき、次数rの正則グラフあるいはr-正則グラフという。<br> | |||
<br> | |||
特に、彩色問題で重要となるのは、次数3の正則グラフである。このグラフは、3次(cubic)グラフともいう。<br> | |||
3次グラフの中で有名な例として、ピーターセングラフがある。<br> | |||
<br> | |||
例<br> | |||
<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> | |||
<br><br> | <br><br> | ||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||