グラフの成分と連結性

グラフは完全に連結していないことがある.例えばWebグラフでは最も大きい強連結成分に含まれるのは25%に過ぎないと推測される.さらに25%は強連結コアの頂点への成分,25%は頂点からの成分,最後の25%はより小さい単独の成分である.ソーシャルグラフについては,限られた方法で繋がっている人々のグループを示す コアの成分が注目されることがよくある.

参照項目参照項目

連結成分

ConnectedComponents 強連結の頂点群を与える

KCoreComponents 最低でも他の 個の頂点と連結されている頂点群を与える

ConnectedGraphQ グラフが連結されているかどうかを検証する

頂点成分

VertexComponent 頂点集合に対する成分を与える

VertexOutComponent ある頂点集合からの成分を与える

VertexInComponent ある頂点集合への成分を与える

頂点の連結性

FindVertexCut 切断するとグラフが切断される最小頂点集合を与える

VertexConnectivity 指定のグラフを切断するために切るべき頂点の最小数

辺の連結性

FindEdgeCut 切断するとグラフが切断される最小辺集合を与える

EdgeConnectivity 指定のグラフを切断するために切るべき辺の最小数

切断と分割

FindMinimumCut 切断する辺を最小化する頂点の分割を求める

FindGraphPartition 切断する辺を最小化する釣合いの取れた頂点の分割を求める

New to Mathematica? Find your learning path »
Have a question? Ask support »