グラフ理論入門 １０ 曲面上のグラフ

10　曲面上のグラフ

10.1　グラフの循環

• 黒頂点に到達したときに、左方向に方向転換、白頂点に到達したときには右方向に方向転換する、という規則で、頂点が白黒に塗られたグラフを移動するようにしてやると、白黒の塗り方は、回路(circuit)を定義していることになる。
• 環状循環(circular rotation)
• 循環ρによってもたらされる回路の個数をr(ρ)で表す。
• スキーム(scheme)
  
  • 頂点に番号をつけ、すべての頂点について、その頂点と隣接する頂点を書き上げたものを、スキームと呼ぶ。
  • グラフの書き下し方法の1つである。
• 循環(rotation)
  
  • ある頂点において、隣接する頂点ラベルを順列として表現すると、スキームになる。

10.2　平面的グラフ・再考

• 連結な平面的グラフ(connected planar graph)
  
  • グラフGが連結で、Gの循環ρでp-q+r(ρ)=2を満たすものが存在するとき、Gは平面的グラフであると呼ぶ。
• 平面的循環(planar rotation)
  
  • 平面的グラフGにおいて、p-q+r(ρ)=2を満たすような循環ρを、平面的循環と呼ぶ。
• 極大(maximal)
  
  • 平面的グラフが極大であるとは、任意の隣接していない2頂点を1辺で結ぶと、得られたグラフが平面的でなくなるときを言う。

10.3　グラフの種類

• 閉曲面(closed surface),境界を持たない曲面(surface without boundary)
• トーラス(torus)
  
  • 種類gの向き付け可能な曲面(orientable surface of genus g)
• 種類(genus,g)
  
  • グラフGを埋没可能な曲面Sgのgの最小値のこと。
  • 平面的なグラフの種類は0である。