グラフ理論入門 ３ 回路とサイクル

３　回路とサイクル

3.1　オイラー回路

• グラフ・多重グラフ・準回路を対象とする。
• 準グラフの用語
  
  • 歩道(walk)
    
    • 準グラフGの歩道とは、Gの頂点と辺の交互列。頂点も辺も繰り返し登場してよい。
  • 開歩道と閉歩道
    
    • 歩道の開始頂点と終了頂点が同じ場合を開歩道(open walk)、異なる場合を(closed walk)と呼ぶ。
  • 歩道の長さ(length)
    
    • 歩道に含まれる辺の個数
  • 小径(trail)
    
    • Gの歩道のうち、どの辺も繰り返さないもののこと。(頂点は繰り返してもよい）
  • 道(path)
    
    • Gの小径でどの頂点も繰り返さないもの。Gがグラフのときには、グラフに対して与えた道と同義。(辺も繰り返さない)
  • 閉小径(closed trail)または回路(circuit)
    
    • 閉歩道であり、小径であるもの。
  • サイクル(cycle)
    
    • 回路のうち、すべての頂点が異なるもの。
  • グラフ・準グラフにおけるサイクル
    
    • グラフの最小サイクルの長さは3であり、これを三角形(triangle)と言う。
  • ループ(loop)と半月形(lune)
    
    • 準グラフには長さ1や2のサイクルが存在する。
    • 長さ1のサイクルをループ、長さ2のサイクルを半月形と呼ぶ。
  • (準グラフにおける)オイラー回路(Eulerian circuit)
    
    • すべての辺とすべての頂点を含む回路のこと。
  • (準グラフにおける)オイラー小径(Eulerian trail)
    
    • Gのすべての辺(とすべての頂点)を含む小径のこと。

3.2　オーバーヴォルファハの問題

• オーバーヴォルファハの問題
• 正則グラフについてのいくつかの定理

3.3　無限格子グラフ

• 無限格子グラフL2の定義
  
  • L2の頂点は、平面上の点でその座標が両方とも整数であるようなもの全体であり、2つの頂点が隣接しているのは、それらの幾何学的距離が1に等しい場合である。
• ハミルトン線、一方向ハミルトン線
  
  • ハミルトンサイクルは、高々、有限個の頂点を持つサイクルであるので、無限格子グラフはハミルトンサイク--ルを持たない。
  • 今、ハミルトン線を次のように定義する。
    
    • 無限グラフL2の連結な2-因子は端点を持たない全域道である。この道は、両方の向きに無限に続く。
    • 1つの端頂点から発し、すべての頂点を通過するような無限に長い道のこと。
• オイラー線、一方向オイラー小径
  
  • 有限グラフに定義されたオイラー小径の無限グラフへの拡張である。
  • どちらの向きにも無限に続くようなオイラー小径のこと。
  • 無限グラフのすべての辺とすべての頂点を含むような小径で、始まりの頂点と終わりの頂点とを持たないもの。
  • 1つの端頂点から発し、無限に続くオイラー小径は一方向オイラー小径と呼ばれる。