13,230
回編集
「第2回 グラフの基礎概念と例」の版間の差分
ナビゲーションに移動
検索に移動
→一般グラフ
編集の要約なし |
(→一般グラフ) |
||
| (同じ利用者による、間の3版が非表示) | |||
| 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> | ||
| 191行目: | 191行目: | ||
<br><br> | <br><br> | ||
== 空グラフ == | == 空グラフ 閉路グラフ 道グラフ 車輪グラフ == | ||
空グラフ(Null graph) | * 空グラフ(Null graph) | ||
m個の点の空グラフを、N<sub>n</sub> | *: 辺集合が空であるグラフのことである。空グラフでは、すべての点が孤立点である。 | ||
*: m個の点の空グラフを、N<sub>n</sub>と表す。下図に、空グラフN<sub>4</sub>を示す。 | |||
* 閉路グラフ(cycle graph) | * 閉路グラフ(cycle graph) | ||
*: 全ての点の次数が2の連結グラフを閉路グラフという。 | *: 全ての点の次数が2の連結グラフを閉路グラフという。 | ||
| 212行目: | 206行目: | ||
<br> | <br> | ||
例<br> | 例<br> | ||
[[ファイル:Graph Theory 2 12.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
| 220行目: | 214行目: | ||
<br> | <br> | ||
例<br> | 例<br> | ||
[[ファイル:Graph Theory 2 13.jpg|フレームなし|中央]] | |||
<br><br> | <br><br> | ||
| 231行目: | 225行目: | ||
<br> | <br> | ||
例<br> | 例<br> | ||
[[ファイル:Graph Theory 2 14.jpg|フレームなし|中央]] | |||
<br> | <br> | ||
空グラフNnは次数0の正則グラフである。<br> | 空グラフNnは次数0の正則グラフである。<br> | ||
| 254行目: | 248行目: | ||
<br> | <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> | <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__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||