第2回グラフの基礎概念と例のソースを表示

== 概要 ==
グラフの基礎概念<br>
* グラフの同形
*: グラフG1とG2が同形である。 ⇔ G1とG2の点の間に1対1対応があり、G1の任意の2点を結ぶ辺数がG2の対応する2点を結ぶ辺数に等しい。
* 次数と握手補題
*: 次数 : 点に接続している辺の本数である。
*: 握手補題 : 任意のグラフのすべての点の次数を合計すれば偶数になる。
* 行列を用いたグラフの表現法
*# 隣接行列 : 点iとjを結ぶ辺の本数をij要素とする行列。
*# 接続行列 : 点iが辺jに接続しているときij要素が1、接続していないとき0であるような行列。
<br>
グラフの例<br>
* 完全グラフ : 相異なる2つの点がすべて隣接している単純グラフ。n個の点をもつ完全グラフをK<sub>n</sub>と表す。<br>K<sub>n</sub>には、<math>\frac{n(n - 1)}{2}</math>本の辺がある。
* 正則グラフ : どの点の次数も同じであるグラフ。次数がrであるとき、r-正則グラフと呼ばれる。
*: ピーターセングラフ
*: プラトングラフ
* 2部グラフ : グラフGの点集合を、互いに同じ要素を持たない集合AとBに分割し、Gの全ての辺はAの点とBの点を結ぶようにしたグラフ。
*: 完全2部グラフ
*: k-立方体
<br><br>




__FORCETOC__
[[カテゴリ:グラフ理論]]