南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第06周 连通度

呵布京大努 NANJING UNIVERSITY 第4章连通度 程龚 2023/3/20

第4章 连通度 程龚 2023/3/20 1

连通的强度 郑 郑 郑 e6 es 宁 ex 宁 03 必 ei 沪 e e3 沪 es e2 ez e2 长 长 长 2023/3/20

2023/3/20 2 连通的强度

本次课的主要内容 4.1块 4.2割集和连通度 2023/3/20 3

4.1 块 4.2 割集和连通度 2023/3/20 3 本次课的主要内容

本次课的主要内容 4.1块 4.2割集和连通度 2023/3/20

4.1 块 4.2 割集和连通度 2023/3/20 4 本次课的主要内容

块 ■块：极大的没有割点的连通子图 V6 V1 V7 ei e3 V5 e6 es V2 VA e2 es 2023/3/20

n 块：极大的没有割点的连通子图 2023/3/20 5 块 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6 v7 v6 e7

块 ■块：极大的没有割点的连通子图 6 、、 e7 V7 e e6 eA V4 e2 e V3 2023/3/20 6

n 块：极大的没有割点的连通子图 2023/3/20 6 块 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6 v7 v6 e7

块 ■块：极大的没有割点的连通子图 ●若G只含1个块，即G连通且没有割点，则G自身称作一个块 e ei e e6 eA N e es 2023/3/20

n 块：极大的没有割点的连通子图 l 若G只含1个块，即G连通且没有割点，则G自身称作一个块 2023/3/20 7 块 v1 v2 v3 v4 e1 e2 e3 e4 e5 v5 e6 v7 v6 e7

块 ■完全图是块吗？ 2023/3/20

n 完全图是块吗？ 2023/3/20 8 块

块 ■完全图是块吗？ ■树是块吗？ 2023/3/20

n 完全图是块吗？ n 树是块吗？ 2023/3/20 9 块

块 ■完全图是块吗？ ■树是块吗？ ■欧拉图和哈密尔顿图是块吗？ 2023/3/20 10

n 完全图是块吗？ n 树是块吗？ n 欧拉图和哈密尔顿图是块吗？ 2023/3/20 10 块