1树的等价刻画
闭卷重建树的等价刻画的对象、状态、事件、不变量与一个失败反例。
离散数学与证明方法 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2根树、遍历与表达式树
闭卷重建根树、遍历与表达式树的对象、状态、事件、不变量与一个失败反例。
3生成树、割与环性质
闭卷重建生成树、割与环性质的对象、状态、事件、不变量与一个失败反例。
4最小生成树与Kruskal
闭卷重建最小生成树与Kruskal的对象、状态、事件、不变量与一个失败反例。
5Prim与优先队列不变量
闭卷重建Prim与优先队列不变量的对象、状态、事件、不变量与一个失败反例。
6Dijkstra与负权边界
闭卷重建Dijkstra与负权边界的对象、状态、事件、不变量与一个失败反例。
7网络流、割与匹配入口
闭卷重建网络流、割与匹配入口的对象、状态、事件、不变量与一个失败反例。
第 1 页 · 背面（答案）
核心机制：根树、遍历与表达式树的核心是：根赋予父子层级，前中后序访问与递归结构对应；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为根树、遍历与表达式树手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：同一无根树选择不同根会改变祖先关系但不改变边。
核心机制：树的等价刻画的核心是：有限无向图连通且m=n−1、无环且m=n−1、任意两点唯一路径等价；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为树的等价刻画手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：只验证边数n−1不能推出是树，还需连通或无环。
核心机制：最小生成树与Kruskal的核心是：按权排序选不成环边，割性质证明每步有安全边；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为最小生成树与Kruskal手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：负权允许，方向图和最短路径不能用MST替代。
核心机制：生成树、割与环性质的核心是：生成树连接全部顶点且无环，向树加边产生唯一环，删环边保持连通；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为生成树、割与环性质手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：不连通图没有生成树但有生成森林。
核心机制：Dijkstra与负权边界的核心是：非负边下每次确定最小暂定距离，松弛保持已知最短上界；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为Dijkstra与负权边界手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：有负边时贪心确定可能错误，需Bellman–Ford等方法。
核心机制：Prim与优先队列不变量的核心是：维护已在树顶点到外部的最轻跨割边，逐步扩展连接区域；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为Prim与优先队列不变量手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：图不连通时只得到一个分量，更新键值不是最终距离。
核心机制：网络流、割与匹配入口的核心是：容量流满足容量和守恒，增广路改进流，最大流最小割连接对偶证据；必须把对象类型、量词、构造或算法不变量和结论同时写清；实验入口：为网络流、割与匹配入口手推最小正常例、边界例和反例，再用有限枚举或结构验证器核对中间状态；边界：残量反向边不是原图负容量，整数容量才直接保证整数流。