* グラフ (graph) [#d7b182de]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

グラフ 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)\) と \((v_j,v_i)\) を区別するとき ''有向グラフ (directed graph)'',区別しないとき ''無向グラフ (undirected graph)'' という.
有向のとき辺の向きは \(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)''

> -- しましま

**関連項目 [#mf2a0a62]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[graph]]
#br
-[[有向グラフ]]
-[[directed graph]]
-[[無向グラフ]]
-[[undirected graph]]
-[[循環グラフ]]
-[[cyclic graph]]
-[[非循環グラフ]]
-[[acyclic graph]]
-[[Hamilton閉路]]
-[[Hamiltonian cycle]]
-[[部分グラフ]]
-[[subgraph]]
#br
-[[グラフィカルモデル]]
-[[グラフマイニング]]
-[[リンクマイニング]]
-[[計算幾何]]
-[[隣接行列]]
-[[Laplace行列]]
-グラフ一覧
--[[超グラフ]]
--[[マルチグラフ]]
--[[二部グラフ]]
--[[木]]
--[[クリーク]]
--[[凸包]]
--[[Voronoi図]]
--[[Delaunay三角形分割]]
--[[Gabrielグラフ]]
--[[相対近傍グラフ]]
--[[最近傍グラフ]]
--[[最小全域木]]
#br
-[[検索:グラフ graph]]

**リンク集 [#j1656599]

//関連するWWW資源があればリンクしてください.
-[[大山崇のホームページ>http://www.nirarebakun.com/]]:いろいろなグラフを描画するJavaアプレット
#br
-[[Wikipedia:Graph_(mathematics)]]
-[[Wikipedia:Graph_theory]]
-[[Wikipedia:Category:Graph_families]]
-[[MathWorld:Graph]]
-[[PlanetMath:Graph]]
-[[PlanetMath:GraphTheory]]
-[[Wikipedia.jp:グラフ]]
-[[Wikipedia.jp:グラフ理論]]

*** Freeware [#k5808417]

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

**関連文献 [#a3904c67]

//この%項目%に関連する書籍や論文を紹介してください.

-[[Book/最適化の手法]] 付録A.3
-[[Book/Algorithms for Clustering Data]] Appendix G

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS