グラフ (graph)

グラフ G は2項組 (V,E).\(V=(v_1,\ldots,v_n)\) はノード (節点,頂点, node,vertex) の集合,E は辺 (枝,edge,arc,branch) の集合.辺は頂点の対 \((v_i,v_j),\;v_i,v_j\in V\).

  • 有向のとき辺の向きは \(v_i\) から \(v_j\).
  • 一つのノードに連結している辺の数をそのノードの 次数 (degree)
  • 二つのノードの間に辺があるときこれらのノードは 連結 (connected) である. 辺が有向のとき,辺の向きに沿っているなら 強連結 (strongly connected),逆向きなら 弱連結 (weakly connected)
  • 辺やノードに重みが割り当てられているものを重み付グラフ (weighted graph).ラベルが付いているものをラベル付グラフ (labeled graph)
  • V中の頂点の全ての対の間に辺が存在するとき 完全 (complete),そうでないとき 不完全 (incomplete)
  • V'⊆V かつ E'⊆E なるグラフ G'=(V',E') をGの 部分グラフ (subgraph)
  • ノードの列 \(v_{i_0},\ldots,v_{i_k}\) について,\(v_{i_j}\) から \(v_{i_j+1}\) j=0…k-1 でへ連結しているとき,この列を パス (路,道,path),同じノードを通過しないパスを 単純路 (simple path)
  • 始点と終点が同じパスを 閉路 (closed path),同じノードを通過しない閉路を 単純閉路 (simple path),全ての頂点を通過する単純閉路を Hamilton閉路 (Hamiltonian cycle)
  • 有向グラフで,強連結の閉路が存在するとき 循環グラフ (cyclic graph),存在しないとき 非循環グラフ (acyclic graph)

-- しましま

関連項目

リンク集

Freeware

グラフマイニング の項を参照

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:20 (2493d)