📢 Webサイト閉鎖と移転のお知らせ
このWebサイトは2026年9月に閉鎖いたします。
新しい記事は移転先で追加しております。（旧サイトでは記事を追加しておりません）
| (同じ利用者による、間の4版が非表示) | |||
| 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> | ||
| 190行目: | 190行目: | ||
[[ファイル:Graph Theory 2 11.jpg|フレームなし|中央]] | [[ファイル:Graph Theory 2 11.jpg|フレームなし|中央]] | ||
<br><br> | <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> | |||
== 正則グラフ == | |||
正則グラフ(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__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||