グラフ理論用語集

グラフ理論の用語集です．

• ループ loop
  • 2端点が同一である辺
• 単純グラフ simple graph
  • 並列辺もループも含まないグラフ
• 多重グラフ multigraph
  • 並列辺やループを含むグラフ
• DAG (Directed Acyclic Graph)
  • 閉路のない有向グラフ
  • 全ての辺が左から右に向くように，各頂点を一直線上に並べることができる．これをトポロジカル順序という．
• トーナメントグラフ
  • 任意の2頂点が1つの有向辺で結ばれているグラフ
• ネットワーク
  • 各辺に実数の重みがつけられているグラフ
• 次数 degree
  • 点vに接続している辺の数をvの次数という
  • 任意のグラフの次数の総和は辺数の2倍に等しい
  • 任意のグラフの奇点は偶数個存在する
  • 全ての点の次数が2以上であるグラフには閉路が存在する
• ウォーク walk
  • 点から始まり点で終わる，点と辺を交互に繰り返す点と辺の系列
  • 辺の数は0でもよい
• トレイル trail
  • 全ての辺が異なるウォーク
• 路 path
  • 点が全て異なるウォーク
  • 路はトレイルである
• 閉ウォーク closed walk
  • 端点が等しいウォーク
• 閉トレイル cosed trail
  • 全ての辺が異なる閉ウォーク
• 閉路 cycle
  • 終点(始点)以外の点が全て異なる長さ(辺の数)が1以上の閉ウォーク
  • 閉路は閉トレイルである
• (強)連結
  • 無(有)向グラフにおいて，任意の2頂点間に路が存在すること
• (強)連結成分
  • (強)連結な頂点集合に分解した際の各集合
• 非連結グラフ disconnected graph
  • 連結でないグラフ
• 連結成分 connected component
  • 極大な連結である部分グラフ
• 木 tree
  • 閉路を含まない連結なグラフ
  • 木の任意の2点は一意的な路で結ばれている
  • 2点以上からなる木には，次数が1の点が2つ以上存在する
• 森 forest
  • 閉路を含まないグラフ
• 独立点集合 independent vertex set
  • グラフの点集合の部分集合のうち，任意の2点が隣接していないもの
• 2部グラフ bipartite graph
  • 点集合を2つの独立点集合に分割できるグラフ
  • グラフが2部グラフであるための必要十分条件は，グラフが奇閉路を含まないこと
• オイラートレイル Euler trail
  • 全ての点と全ての辺を含むトレイル
• オイラー閉トレイル Euler losed trail
  • 全ての点と全ての辺を含む閉トレイル
• 準オイラーグラフ
  • オイラー閉路は含まないが，オイラー路は含むグラフ
• オイラーグラフ Euler graph
  • オイラー閉トレイルが存在するグラフ
  • 必要十分条件は，全ての点が偶点
  • 一筆書き
• 完全グラフ complete graph
  • 全ての異なる2点が辺で結ばれているグラフ
• ハミルトン路 Hamilton path
  • グラフの全ての点を含む路
• ハミルトン閉路 Hamilton cycle
  • グラフの全ての点を含む閉路
• 準ハミルトングラフ
  • ハミルトン閉路は含まないが，ハミルトン路は含むグラフ
• ハミルトングラフ hamiltonian graph
  • ハミルトン閉路の存在するグラフ
  • 必要十分条件となる特徴づけは知られていない
  • 巡回セールスマン問題を解けば，ハミルトングラフ判定が可能