南京大学：《图论与算法》课程教案讲稿（Graph Theory and Algorithms, GTA）第05周 圈和遍历

呵力京大努 sof NANJING UNIVERSITY 第3章圈和遍历 程龚 2023/3/13

第3章 圈和遍历 程龚 2023/3/13 1

为什么专门讨论“圈” ■ 圈是图结构复杂性的主要表现之一 ■一些图论中的难问题在不含圈的图上较容易解决 2023/3/13

n 圈是图结构复杂性的主要表现之一 n 一些图论中的难问题在不含圈的图上较容易解决 2023/3/13 2 为什么专门讨论“圈

上次课讨论的“遍历 确保爬过（有可能爬到的）所有顶点， 并减少不必要的重复爬行 V3 es VA 2023/3/13 3

n 确保爬过（有可能爬到的）所有顶点， 并减少不必要的重复爬行 2023/3/13 3 上次课讨论的“遍历” v1 v2 v3 v4 e1 e2 e4

本次课讨论更严格的“遍历” 2023/3/13 4

2023/3/13 4 本次课讨论更严格的“遍历

本次课讨论更严格的“遍历” e V2 e6 小0 e es 9 2023/3/13

2023/3/13 5 本次课讨论更严格的“遍历

本次课讨论更严格的“遍历” 3 4 2023/3/13

2023/3/13 6 本次课讨论更严格的“遍历

本次课讨论更严格的“遍历” 3 4 e2 e3 VA eg ex es v6 V5 e1o e6 e11 8 es e V7 2023/3/13 >

2023/3/13 7 本次课讨论更严格的“遍历

本次课的主要内容 3.1圈和树 3.2二分图 3.3欧拉图 3.4哈密尔顿图 2023/3/13

3.1 圈和树 3.2 二分图 3.3 欧拉图 3.4 哈密尔顿图 2023/3/13 8 本次课的主要内容

本次课的主要内容 3.1圈和树 3.2二分图 3.3欧拉图 3.4哈密尔顿图 2023/3/13

3.1 圈和树 3.2 二分图 3.3 欧拉图 3.4 哈密尔顿图 2023/3/13 9 本次课的主要内容

圈和树 ■闭路线：起点和终点相同的非平凡路线 e2 es V3 V4 V2 eg es e es V5 e10 e6 e8 e 2023/3/13

n 闭路线：起点和终点相同的非平凡路线 2023/3/13 10 圈和树 v1 e1 v2 v3 v6 v8 v4 v5 v7 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11