1
第二章 图的连通性
在第一章中已经定义连通图是任二顶点间都有路相连的图。 对于连通图, 其连通的程度
也有高有低。例如,下列三个图都是连通图。对于图 G1,删除一条边或一个顶点便可使其
变得不连通;而对于图 G2,至少需要删除两条边才能使其不连通,也可以删除一个顶点使
其不连通;对于图 G3,要破坏其连通性,则至少需要删除三条边或三个顶点。
本章主要讨论如何通过图的顶点集、 边集和不交的路集合的结构性质来获知图的连通性
程度。通过研究割边和割点来刻画 1连通图的特性; 定义连通度和边连通度来度量连通图连
通程度的高低;通过不交路结构和元素的共圈性质来反映图的 2连通和 k连通性。
§2.1 割点和割边
定义 2.1.1 设 )(GVv∈ ,如果 )()( GwvGw >- ,则称 v为 G 的一个 割点 。
(注:该定义与某些著作中的定义有所不同, 主要是在环边的顶点是否算作割点上