グラフの成分と連結性

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

参照項目参照項目

連結成分

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

WeaklyConnectedComponents 弱連結の頂点群を与える

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

ConnectedGraphQ  ▪  WeaklyConnectedGraphQ

頂点成分

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

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

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

頂点の連結性

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

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

KVertexConnectedComponents k 頂点連結成分を与える

KVertexConnectedGraphQ グラフが k 頂点連結であるかどうかを検証する

辺の連結性

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

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

KEdgeConnectedComponents k 辺連結成分を与える

KEdgeConnectedGraphQ グラフが k 辺連結であるかどうかを検証する

切断と分割

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

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