MIT计算机科学数学课程：有向图传递性性质的困惑求解

嘿，我刚好啃过MIT这门离散数学的内容，来帮你理清这个问题～

首先，咱们先把传递性的定义抠得更严谨一点：

对于有向图中的任意三个顶点 (u, v, w)，如果存在边 (u \to v) 和 (v \to w)，那么必须存在边 (u \to w)。

你提到的v₂→v₃、v₃→v₄且存在v₂→v₄，这一组确实符合传递性要求，但传递性需要覆盖所有满足“u→v且v→w”的组合，而不是只看其中一组。

咱们结合课程讲义里这个经典例子的常见情况来分析：

• 比如图中存在边 (v_1 \to v_2) 和 (v_2 \to v_3)，但没有边 (v_1 \to v_3) —— 这就直接违反了传递性；
• 或者存在边 (v_1 \to v_3) 和 (v_3 \to v_4)，但没有边 (v_1 \to v_4)；
• 再或者有边 (v_2 \to v_4) 和 (v_4 \to v_1)，但没有对应的 (v_2 \to v_1) 边。

这些未被满足的“u→w”边，就是你之前忽略的点。传递性的核心是全局所有符合条件的三元组都要满足推导要求，不是某一组符合就可以哦。

你可以再仔细对照图7.8里的所有边，把所有形如“u→v且v→w”的组合列出来，逐一检查是否存在对应的u→w边，就能精准找到那个违反传递性的组合了。

内容的提问来源于stack exchange，提问作者Stone