第2回 グラフの基礎概念と例

概要

グラフの基礎概念

• グラフの同形

  グラフG1とG2が同形である。 ⇔ G1とG2の点の間に1対1対応があり、G1の任意の2点を結ぶ辺数がG2の対応する2点を結ぶ辺数に等しい。

• 次数と握手補題

  次数 : 点に接続している辺の本数である。

  握手補題 : 任意のグラフのすべての点の次数を合計すれば偶数になる。

• 行列を用いたグラフの表現法
  1. 隣接行列 : 点iとjを結ぶ辺の本数をij要素とする行列。
  2. 接続行列 : 点iが辺jに接続しているときij要素が1、接続していないとき0であるような行列。

グラフの例

• 完全グラフ : 相異なる2つの点がすべて隣接している単純グラフ。n個の点をもつ完全グラフをK_nと表す。
  K_nには、${\frac {n(n-1)}{2}}$本の辺がある。
• 正則グラフ : どの点の次数も同じであるグラフ。次数がrであるとき、r-正則グラフと呼ばれる。

  ピーターセングラフ

  プラトングラフ

• 2部グラフ : グラフGの点集合を、互いに同じ要素を持たない集合AとBに分割し、Gの全ての辺はAの点とBの点を結ぶようにしたグラフ。

  完全2部グラフ

  k-立方体