有向图：度数、walk 与 path
Vertex Degrees · Walks & Paths有向图（digraph）= 二元关系换上视觉外衣：点叫顶点，关系对 ⟨u→v⟩ 叫有向边（u 是尾、v 是头）。每个顶点有入度 indeg 与出度 outdeg；全图所有顶点的入度之和与出度之和恒相等，都等于边数（握手引理 10.1.2）。
walk 是沿着箭头走的顶点-边交替序列（如原书式 10.1 在整除图上走的 1 → 2 → 4 → 12 → 12 → 12），path 是不重复访问顶点的 walk；起点终点相同的 walk 叫闭合 walk；长度为正、除首尾外顶点互异的闭合 walk 叫圈（cycle）——单个顶点是长度 0 的闭合 walk，不算圈。原书 371 页在 4 节点图 H 上给了七个判例——abd 是 path、⟨a→b⟩⟨b→d⟩ 是同一条 path 的边序列写法、abcbd 只是 walk、dcbcbd 是闭合 walk、bdcb 是圈、(b→c)(c→b) 是长 2 圈，而 (c→b)(b→a)(a→d) 压根不是 walk（逆行违规）。基本定理 10.2.3：最短的 walk 必是 path——同一顶点走两次，删掉中间的环只会更短（良序原理保证从 u 到 v 的 walk 中存在最短者；若它重复经过某顶点，删掉中间一段得到更短的 walk，与最短性矛盾）。距离 dist(u,v) 定义为最短 path 长度，满足三角不等式（引理 10.2.5）；原书习题 10.3 正是让你证"取等 ⟺ x 在 u 到 v 的最短 path 上"。
邻接矩阵的幂：用乘法数 walk
Adjacency Matrices把有向图写成 n×n 的 0/1 邻接矩阵 A_G，神奇的事情发生了：(A_G)^k 的 (u,v) 元恰好是从 u 到 v 的长度 k walk 的条数（定理 10.3.2 + 推论 10.3.3）。拿原书 4 节点图 H 试一试——注意 a 到 c 的长度 2 walk 恰有 2 条（a→b→c 与 a→d→c）：
10.4walk 关系与传递闭包
把"是否存在 walk"本身看成一个关系：walk 关系 G*（u G* v ⟺ 有 walk 从 u 到 v）与正 walk 关系 G⁺（要求长度 > 0）。关系复合 Gⁿ 恰是"长度 n walk"关系（习题 10.11），而每个 path 长度 ≤ |V|−1，于是（原书式 10.9）：
这就是可达性：不必走无穷多步，把前 n 个幂取并即可（还可重复平方加速）。10.5 节的先修课关系也靠它：修课资格由 D⁺ 判定，若 D⁺ 出圈（有闭合 walk）你就永远毕不了业——所以先修图必须是 DAG。
DAG 与并行调度
Directed Acyclic Graphs & Scheduling原书 Figure 10.7 的经典例子：正式场合的穿衣流程是一个 DAG（有向无圈图）——先袜后鞋、内衣在裤前、衬衫在领带前……拓扑排序给出一个合法顺序；而有无限多台"处理器"时，并行时间 = critical path 的长度（推论 10.5.9）——即最长链的大小。穿衣服的 critical path 只有 4 步：衬衫 → 裤子 → 腰带 → 外套（或内衣→裤子→腰带→外套）。
10.5.1拓扑排序：一次穿一件
拓扑排序（Definition 10.5.2）= 把全部顶点排成一列，每个顶点都在它可达的顶点之前。构造法（原书正文）：反复从当前 minimal 元素（没有未完成前驱的顶点）里任选一个放进队尾——原书 Figure 10.8 就这样得到两个不同的合法解。定理 10.5.4：每个有限 DAG 都有拓扑排序——"早上能穿好衣服"的数学证明。
n 个顶点的 DAG 若最长链只有 t，则顶点可划分成 t 个反链（antichain，两两不可达）。推论 10.5.13：任何 n 元偏序集必有大小 ≥ √n 的链或大小 ≥ √n 的反链。
偏序、集合包含与类型鉴定
Partial Orders · Set ContainmentDAG 的 walk 关系自带三条性质：传递（引理 10.6.2，walk 合并即传递）、反自反（DAG 无圈 ⇒ 走不回自己）、由此得 asymmetric（推论 10.6.10）。满足传递 + 反自反（等价地：传递 + asymmetric，推论 10.6.11）的关系叫严格偏序（strict partial order）——定理 10.6.8 说它恰是某个 DAG 的正 walk 关系。把 asymmetric 放宽为 antisymmetric（允许自反）再加自反，就是弱偏序（Definition 10.6.13）：≤、⊆、整除 | 全是；推论 10.6.15：弱偏序 ⟺ 某个 DAG 的 walk 关系。原书练习还提示两个"平凡"判例：恒等关系 Id_D 是弱偏序，空关系是严格偏序。
10.8 节给偏序"排队"：线性序 = 任意两个不同元素都可比较（≤、< 是；⊆、先修关系不是）。10.9 节的积序按分量比较：原书 Example 10.9.2 的"更年轻且更矮"积序 Y 上，Dilworth 引理保证 101 个学生里必有 11 人"越大越高"（链）或 11 人"越小越高"（反链）。
10.7用集合包含画偏序（10.7）
公理抽象，但"满足公理的东西长什么样"最好有图。定理 10.7.3：每个弱偏序都同构于某集合族上的 ⊆（严格偏序则同构于 ⊂）——偏序"长得都像集合包含"。构造法：把元素 a 映到它的"下闭包"{b : b ≤ a}。原书用整除关系 {1,3,4,6,8,12} 演示：3 | 12 ⟺ {1,3} ⊆ {1,3,4,6,12}。
等价关系：划分的另一面
Equivalence Relations等价关系（自反 + 对称 + 传递）是偏序的"镜像亲戚"：偏序把元素排成层级，等价关系把元素捏成团块。任何全函数 f 都自带等价关系 ≡_f（a ≡_f a′ ⟺ f(a) = f(a′)，Definition 10.10.2），≡ (mod n) 正是 f = 余数函数的特例。等价类 [a]ᴿ 把集合切成两两不交的块，反过来任何划分也生成一个等价关系——"等价关系 ⟺ 划分"（定理 10.10.4）：≡ (mod 5) 的五个块 {…,−5,0,5,10,…}、{…,−4,1,6,11,…}……把整数切成五段，正对应第九章的"mod 5 五个世界"。
习题实战
Practice Problems, Playable两道原书 Practice Problem 做成解题器：先自己算，再点选核查。
终局自测
Final Check八题，覆盖 10.1–10.10 全部小节。
彩蛋与课后挑战
Easter Eggs & ProblemsPageRank 的史前史（原书 10 章开头）
万维网就是一个亿万顶点的有向图：页面是点、超链接是箭头。1995 年 Stanford 的两个学生 Larry Page 和 Sergey Brin 意识到这个图的结构可用于搜索——后来的事大家都知道了。"pay attention to graph theory, and who knows what might happen!"（原书原话）
德布鲁因序列与鸡群之王（原书习题 10.5 / 10.13）
10.5：把全部 8 个 3-bit 串作为连续 3 位窗口塞进一条尽量短的线性串——0001011100（长 10 = 2³ + 2，恰为最小：8 个窗口 000,001,010,101,011,111,110,100 一个不缺）。这就是 de Bruijn 序列 B(2,3) 的线性化；2-bit 版本的图已在原书 Figure 10.10，习题 10.7 解释了为什么"每边恰走一次"的 Euler 型路径必然存在。10.13 鸡群之王：出度最大的鸡必然"virtual peck"所有其他鸡（King Chicken Theorem）——竞赛图（tournament digraph）的入门礼。
课后挑战（均出自原书习题）
- 10.2 用对箭头数的归纳证明握手引理（Σ indeg = |graph|）。
- 10.7 证明：弱连通有向图中每点入度 = 出度 ⟺ 存在 Euler tour（经过每条边恰一次的闭合 walk）。
- 10.16 把 1..10000 排成一个序列，使其中不存在长度 101 的递增或递减子序列（Erdős–Szekeres 的构造版）。
- 10.30 证明有限严格偏序的"最小 DAG"（HASSE 图）唯一且易找。