离散数学与证明方法 · 小纸条

核心机制：路径、回路与连通性的核心是：路径限制顶点重复，迹限制边重复，连通分量是最大连通子图；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为路径、回路与连通性手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：walk、trail、path不能混用，方向图还区分强弱连通。

核心机制：图、子图、度与握手定理的核心是：图由顶点边定义，度数和等于边数两倍，可用于奇度顶点计数；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为图、子图、度与握手定理手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：简单图、多重图和有向图的度定义不同。

核心机制：BFS与最短无权路径的核心是：BFS按层扩展，首次发现距离等于最少边数并形成最短路径树；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为BFS与最短无权路径手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：带权图不能直接用普通BFS，父节点选择不同但距离应相同。

核心机制：邻接表、矩阵与稀疏性的核心是：表示选择决定时间空间代价，邻接表适合稀疏遍历，矩阵适合常数邻接查询；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为邻接表、矩阵与稀疏性手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：复杂度必须写n与m，不能只说快。

核心机制：二分图与奇环的核心是：二分图等价于可二着色，也等价于没有奇环；冲突边可恢复反例；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为二分图与奇环手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：局部两色成功不代表全图成功，必须遍历每个分量。

核心机制：DFS、时间戳与边分类的核心是：DFS递归深入并给发现完成时间，支持环、拓扑和割结构分析；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为DFS、时间戳与边分类手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：无向图父边不能误判回边，递归栈与已访问含义不同。

核心机制：欧拉路与哈密顿问题的核心是：欧拉关注每条边，哈密顿关注每个顶点；前者有度条件，后者一般困难；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为欧拉路与哈密顿问题手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：两个名字相似但判据与计算难度完全不同。