图论讲义61
需积分: 0 53 浏览量
2022-08-03
20:51:13
上传
评论
收藏 281KB PDF 举报
§3.2 块
块：没有割点的连通图称为块。至少有 3 个顶点的块是 2 连通的。
一个图的块是指该图的一个子图，这个子图本身是块，而且是有此性
质的块中的极大者。
例子：（见图 3.3）
内部不相交的路：G 中一族路称为内部不相交的，如果 G 中没有这
样的顶点，它是这族路中一条以上的路的内部顶点。
例子：
定理 3.2：一个 的图 G 是 2-连通的，当且仅当 G 的任意两个顶
点至少被两条内部不相交的路所连。
证：若 G 的任意两个顶点至少被两条内部不相交的路所连，则显然，
G 是连通的，并且没有 1 顶点割。因此 G 是 2 连通的。
反之，设 G 是 2 连通的。对 u 和 v 之间的距离 用归纳法来证
明：任意两个顶点 u 和 v 至少被两条内部不相交的路所连。
首先假设
。由于 G 是 2 连通的，因此边 uv 不是割边，
由定理 2.3，它包含在某个圈中。由此推出：u 和 v 被 G 的两条内部
不相交的路所连。
现在假设对于距离小于 k 的任意两个顶点定理均成立，并且设
。考察长为 k 的一条 路，并且设 w 是该路上 v 前
面的那个顶点。因为
，由归纳假设可知：在 G 中有两
条内部不相交的 路 P 和 Q。又因为 G 是 2 连通的，所以 是
点连通度于等于2的连通图
Friday永不为奴
- 粉丝: 12
- 资源: 317
评论0