有向依赖作业合法序列中相邻作业交换判定规则及证明咨询

这个交换规则是成立的，它属于DAG（有向无环图）拓扑排序的经典相邻交换性质，有严谨的理论支撑。

你给出的判断逻辑刚好切中了合法拓扑序列的相邻节点特性：

• 合法拓扑序列的核心要求是：对任意依赖边 u→v（u必须在v之前执行），u在序列中一定出现在v的前面。
• 如果两个相邻节点u（左）、v（右）在合法序列中出现，首先不可能存在v是u前驱的情况，否则会违反合法序列的要求。
• 如果u是v的间接前驱，那么必然存在至少一个中间节点x形成路径 u→x→…→v，x必须出现在u和v之间，因此u和v不可能相邻。
  也就是说，合法拓扑序列的相邻节点只有两种可能：要么u是v的直接前驱，要么u和v完全没有依赖关系。因此你只需要判断u是不是v的直接前驱，不是的话就可以安全交换，交换后的序列依然合法。

前提：G为作业依赖对应的DAG，S是G的合法拓扑序列，取S中相邻节点u（位置i）、v（位置i+1），且u不是v的直接前驱。

1. 由于S是合法序列，不存在边 v→u，否则v作为u的前驱必须出现在u之前，和当前u在v前的顺序矛盾。
2. 假设u是v的间接前驱，则存在路径 u→x₁→x₂→…→xₖ→v（k≥1），根据拓扑序列要求，所有x₁到xₖ必须出现在u之后、v之前，和u、v相邻的前提矛盾，因此u和v不存在任何依赖关系。
3. 交换u和v得到新序列S'：
   • u的所有前驱原本都在位置i左侧，交换后依然在u左侧；u的所有后继原本都在位置i+1右侧，交换后依然在u右侧，满足依赖要求。
   • v的所有前驱原本都在位置i左侧，交换后依然在v左侧；v的所有后继原本都在位置i+1右侧，交换后依然在v右侧，满足依赖要求。
     因此S'也是G的合法拓扑序列。

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