我一直在使用我编写的一个小蟒蛇脚本来管理我的室友之间的债务。它有效，但有一些缺失的功能，其中之一是简化不必要的复杂债务结构。例如，如果下面的加权有向图代表某些人，而箭头代表他们之间的债务（Alice欠Bob 20美元和Charlie $ 5，Bob欠Charlie 10美元，等等）：
很明显，该图应简化为下图：
如果爱丽丝可以直接将它交给查理，10美元从艾丽丝到鲍勃，然后从鲍勃到查理，没有任何意义。
那么，在一般情况下，目标是采用债务图并简化它（即产生具有相同节点但不同边缘的新图），使得
通过“流量”，我的意思是所有输入的值减去所有输出（这是否有技术术语？我不是图论专家）。所以在上面的例子中，每个节点的流量值是：
您可以看到第一个和第二个图表在每个节点上具有相同的流量，因此这是一个很好的解决方案。还有一些其他简单的情况，例如，可以通过移除最低值边缘并从所有其他边缘减去其值来简化任何循环。
这个：
应简化为：
我无法想象没有人研究过这个问题;我只是不知道要搜索哪些术语来查找信息（再次，不是图论专家）。我一直在寻找几个小时无济于事，所以我的问题是：根据上面针对任何加权有向图指定的条件，什么算法会产生简化（新图）？
您可以在O（n）中找到期望获得或支付多少钱。所以你可以简单地创建两个列表，一个用于借记，另一个用于信用，然后平衡两个列表的头部直到它们为空。从你的第一个例子：
事务定义图表的边缘。对于涉及的n个人，最多将有n-1个交易=边缘。最初，两个列表的总长度为n。在每个步骤中，至少一个列表（借方/贷方）缩短一个，最后两个清单一次消失。
问题在于，一般来说，这个图不必与原始图类似，因为我认为这是一个要求。 （是吗？有些情况下，最优解决方案包括增加新的边缘。想象一下A欠B和B，因为C的金额相同，A应该直接支付C，但这个边缘不在债务图中。）
如果目标只是构建一个等价图，您可以搜索债权人和债务人名单（如上节所述）进行完全匹配，或者信用总额与一个人的借方相匹配的情况（或者反之亦然） ）。寻找bin packing。对于其他情况，除了拆分流之外你别无选择，但即使是上面的简单算法，也会生成一个图表，其边缘比所涉人员少一个 - 最多。
编辑：感谢j_random_hacker指出如果有一组人的总债务与另一组人的信用相匹配，那么边界少于n-1的解决方案是可能的：然后，问题可以分成两个子问题：事务图的总成本为n-2个边。不幸的是，subset sum problem是NP难的。
也许这也可以转变为min-cost flow problem。如果您只想简化原始图表，则在其上构建流程，边缘容量是借方/贷方的原始金额。债务人充当流入节点（通过连接器节点，为所有债务人服务，其容量边缘等于其总债务），债权人用作流出节点（具有类似的连接器节点）。
如果您想最小化交易数量，您更愿意保留“大”交易并减少“小”交易。因此，每个边缘的成本可以被建模为该边缘上的流量的倒数。
这是一篇学术论文，详细研究了这个问题。最后，第8节中还有一些不同算法的示例代码。
我实际上遇到了与你完全相同的问题:)
我认为krlmlr的各种解决方案并不能完全解决问题。我会考虑如何准确地解决它（在最小边缘意义上），但与此同时，一个实际的替代解决方案是发明一个新人，史蒂夫：
如果一个欠钱的人不能立刻支付全部费用，他们可以给史蒂夫他们现在负担得起的东西，并将这笔金额从他们的姓名中扣除全部欠款。同样地，如果你欠的钱比史蒂夫现有的钱多，你可以拿走他现有的所有钱，并从你的名字中扣除欠款。
如果每个人在开始时只同意向史蒂夫支付全额金额，那么每个网络人员只需支付一笔存款，而每个网民都只能提取一笔（尽管这可能需要对史蒂夫进行多次检查以确定他目前是否有足够的资金手上的现金）。史蒂夫的好处在于他总是在身边，而且从不忙于理清财务状况。不幸的是，他很容易上当受骗，所以爱丽丝，鲍勃和查理需要彼此信任，不要利用他。