同类型流路径压缩：如何简化合作图中的中转关系

在合作方案的图表示中，节点代表参与者，边记录谁向谁提供什么、数量是多少。一段关系可能先经过中转方，再到达接收方。发现引擎里的 shrink_ring 函数接收这样的候选图和一个指定的中转节点，在类型、单位与局部连接满足条件时，用一条直接边替换两条中转边。它是候选方案的局部图变换，输出仍需要回到实际安排中核对，不能自动移除现实中的参与者。

有些合作方案画出来很复杂，是因为同一种东西经过了好几个人的手。甲交给中转方，中转方再交给乙。如果中转方只是转交，能不能直接把甲和乙连起来？

这听起来像删掉一个节点。真正要先回答的却是：删掉以后，剩下的那条线究竟代表什么，数量又应该是多少？

下面先用一个三方流转例子计算替换边，再检查哪些条件允许压缩，以及压缩会留下什么信息。

沿用代码测试的构造例子：甲向中转方提供 8 个资金单位，中转方向乙提供 6 个相同单位，乙另向甲交付 1 件物品。这只是用于检验图变换的小例子，没有发生实际付款。

甲 ── 8 单位资金 ──→ 中转方 ── 6 单位资金 ──→ 乙
↑                                            │
└──────────────── 1 件物品 ───────────────────┘

如果把中间两段换成“甲直接向乙提供 8”，我们就多写出了 2 个原先没有到达乙的单位。如果写成 14，则把同一路径上的流量重复加了一遍。这个局部操作取的是两段数量的较小值：

直接边的数量 = min(进入量, 离开量) = min(8, 6) = 6

变换后，图里剩下“甲向乙提供 6 个资金单位”和“乙向甲交付 1 件物品”两条边。参与这段转交的共同数量是 6。原来进入侧多出的 2，没有被自动分给任何人，也没有作为一条余额边保留在新图里。

这最后一点会影响我们怎样使用结果。新图表达的是抽取出来的共同流量，不能据此声称原图的所有收支、义务和余额都被完整保留了。实现同时返回原边编号，便于回到输入检查被压缩的两段；若后续需要处理那 2 个单位，就必须另外保留并解释原来的安排。

把离开量从 6 改成 10，直接边会变成 8。换成 8 进 8 出，才会得到两段数量完全相同的压缩。由此可以看出，操作没有在替整张图寻找最优分配，它只回答一条给定的两段路径能提取出多少共同流量。

“8”和“6”只有在指同一种东西时才有可比性。8 小时教学和 6 件工具，即使连在同一个人身上，也不能压成一条数量为 6 的关系。把人民币和另一种货币都写成“资金”，也不足以直接比较。

因此，函数先检查两条边的资源类型和单位完全相同。中间节点还必须恰好只有一条进入边、一条离开边。如果有两个供应者、三个接收者，哪一份供应对应哪一项输出已经需要分配规则，当前函数会拒绝继续。

另一个检查针对附带条件。假设中转方承诺“物品通过检验后再付款”，直接跳过他可能也跳过了检验。实现会拒绝带有条件引用的这两条边，让条件先被处理。

这些检查为什么放在最前面？因为取较小值这个算式本身没有能力判断交易含义。只有类型、单位和局部结构符合要求，那个数才具有这里所需的解释。

但代码中的“没有条件引用”，仍然只是输入图的一个事实。如果实际参与者承担保管、担保、协调、收费或审查职责，而这些职责没有被写进图，函数不会自行发现它们。图允许压缩，不等于现实允许把这个人移除。候选路径最终仍需要相关主体确认。

这项计算和网络流里的路径瓶颈有直接联系：一条串联路径能够继续送出的流量，受最紧的那一段限制。在最大流算法中，沿一条增广路径增加流量时，也要先找这条路径上的最小剩余容量。普林斯顿的算法教材给出了这一过程。最大流教材与实现

不过，最大流还要维护整个网络的容量、流量和剩余网络，并反复选择路径。本地这个函数没有做这些事情，也没有计算总流量的最大值。它使用了相同的局部瓶颈思想，完成的是一次候选图改写。这个关系可以从计算中看出来；现有材料不足以把它写成团队当初明确沿着最大流算法设计过来的历史。

我们也可以保留中转节点。节点如果承担独立服务，保留它往往使方案更准确。压缩值得考虑的场合，是先前的表示把一段纯转交写得过长，而读者或后续求解器需要看见端点之间可直接讨论的关系。

当前能确认的效果很具体：在这个构造例中，三条边变成两条，直接资金边取值为 6；类型不符、存在条件、连接不唯一时拒绝改写。它没有证明真实协调成本下降，也还没有形成一条已经投入使用的自动去中转流程。

这项小算法提醒我们，简化图要同时回答两个问题：哪些信息变得更清楚，哪些信息被留在了原图中。只要这两个答案可追踪，简化就能帮助下一次讨论；若把一张更短的图当作已经完成的现实安排，删掉的很可能恰好是责任。

实现与证据。 路径压缩函数（实现定位保留于编辑档案）；原构造测试（实现定位保留于编辑档案）。本文复算的是局部图变换，不是生产流转。函数用浮点数处理数量，本文使用整数例子；不能据此推导财务记账精度保证。

本篇另备有明亮、适合手机连续阅读的公众号排版稿，配图按照本文机制单独绘制。查看公众号版，或下载 Markdown、HTML、PNG 与 SVG 配图包。