13,009
回編集
「第2回 グラフの基礎概念と例」の版間の差分
ナビゲーションに移動
検索に移動
→2部グラフと完全2部グラフ
編集の要約なし |
|||
| 256行目: | 256行目: | ||
<br><br> | <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> | |||
<br><br> | |||
== 単純グラフの補グラフ == | |||
単純グラフGの補グラフ(Complement graph)Gとは、Gと同じ点集合V(G)をもち、<br> | |||
Gの2点が隣接するのはGにおけるそれら2点が隣接していないときかつそのときに限るような単純グラフである。<br> | |||
補グラフは、相補グラフともいう。<br> | |||
<br> | |||
完全グラフの補グラフは空グラフである。<br> | |||
完全2部グラフの補グラフは2つの完全グラフの和である。<br> | |||
<br> | |||
例<br> | |||
<br><br> | |||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:グラフ理論]] | [[カテゴリ:グラフ理論]] | ||