我一直在使用我编写的一个小Python脚本来管理室友之间的债务。它有效，但缺少一些功能，其中之一是简化不必要的复杂债务结构。例如，如果下面的加权有向图代表一些人，箭头代表他们之间的债务（爱丽丝欠鲍勃 20 美元，查理欠 5 美元，鲍勃欠查理 10 美元，等等）：
很明显，这个图应该简化为下图：
如果爱丽丝可以直接把 10 美元给查理，那么 10 美元从爱丽丝到鲍勃，然后从鲍勃到查理是没有意义的。
那么，在一般情况下，目标是获取债务图并简化它（即生成具有相同节点但不同边的新图），以便
- 没有节点有既指向内部又指向外部的边缘（没有无用的钱易手）
- 所有节点都具有与原始图中相同的“流量”（资金最终流向相同）。
我所说的“流量”是指所有输入减去所有输出的值（有专门的术语吗？我不是图论专家）。因此，在上面的示例中，每个节点的流量值为：
您可以看到第一张图和第二张图通过每个节点的流量相同，因此这是一个很好的解决方案。还有一些其他简单的情况，例如，可以通过删除最低值的边并从所有其他边中减去其值来简化任何循环。
This:
应简化为：
我无法想象没有人研究过这个问题；我只是不知道要搜索哪些术语来查找相关信息（同样，不是图论专家）。我已经寻找了几个小时但没有结果，所以我的问题是：什么算法可以根据上面为任何加权有向图指定的条件生成简化（新图）？
这是一篇学术论文，详细研究了这个问题。第 8 节最后还有一些不同算法的示例代码。
韦尔霍夫，T.（2004）。有效解决多重债务：计算科学的邀请。教育信息学，3(1), 105-126。 https://research.tue.nl/en/publications/settling-multiple-debts-efficiently-an-invitation-to-computing-sc
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
