图论与组合 · 已有部分内容
第 4 章 连通度和路径
从点割、边割与块的结构，推进到不相交路径，再把连通问题与网络流联系起来。
知识点与笔记
-
4.1 割和连通度
中文教材 p.117 起。比较点连通度、边连通度和块，理解删除顶点或边对连通性的影响。
-
4.2 k-连通图
中文教材 p.126 起。学习 2-连通、有向图连通性、k-连通与 Menger 定理的应用。
-
4.3 网络流问题
中文教材 p.138 起。讨论最大网络流、整数流，以及供给和需求的选学模型。
习题与资料
点连通度与 Harary 图
对应 §4.1 的点连通部分：点割、连通度、完全图与超立方体例子及 Harary 图。
Connectivity and Paths
Hengjia Wei，Chapter_4___Connectivity_and_Paths.pdf；割与连通 PDF pp.3-32，k-连通图 pp.33-83，网络流 pp.84-124。
教材定位：中文教材第 4 章，§4.1-§4.3，pp.117-150；目录见 PDF 第 2-3 页。教师 Chapter 4 讲义的三个部分与本章三节对应。