图分量与连通性

图可能没有完全连通. 比如说,在最大的强连通分量中,估计只有大约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 求顶点的平衡割集,使得删除的边最少