sponsored links

图论

连通图的割点、割边(桥)、块、缩点,有向图的强连通分量

November 30
连通图的割点、割边(桥)、块、缩点,有向图的强连通分量
连通图的割点.割边(桥).块.缩点,有向图的强连通分量   [本文摘选自百度文库] 一.基本概念 无向图 割点:删掉它之后(删掉所有跟它相连的边),图必然会分裂成两个或两个以上的子图. 块:没有割点的连通子图 割边:删掉一条边后,图必然会分裂成两个或两个以上的子图,又称桥. 缩点:把没有割边的连通子图缩为一个点,此时满足任意两点间都有两条路径相互可达. 求块跟求缩点非常相似,很容易搞混,但本质上完全不同.割点可以存在多个块中(假如存在k个块中),最终该点与其他点形成k个块,对无割边的连通子图进行