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

連結成分

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

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

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

ConnectedGraphQ  ▪  WeaklyConnectedGraphQ  ▪  ConnectedGraphComponents  ▪  WeaklyConnectedGraphComponents

頂点成分

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

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

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

VertexOutComponentGraph  ▪  VertexInComponentGraph

頂点の連結性

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

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

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

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

辺の連結性

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

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

KEdgeConnectedComponents — k 辺連結成分を与える

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

切断と分割

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

FindMaximumCut — カットする辺を最大にする頂点の分割を求める

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