1回答
据我所知，找到最小流量的最简单方法是利用最小切割~最大流量对偶，并使用推挽算法进行最大流量计算。但是推挽算法并没有给我们任何关于、S、和T集的信息。
那么，获得S和T最小剪切子集的正确方法是什么？有一种方法可以使用推挽算法吗？这在C++或Python中有实现吗？
浏览 6提问于2013-07-16得票数 1
3回答
动态图中的最大流
、、
我正在寻找快速算法来计算动态图中的最大流量(添加/删除具有相关边的节点到图中)。也就是说，我们在G中有了最大流，现在添加/删除了带有相关边的新节点，我不喜欢重新计算新图的最大流，实际上，我想使用以前的结果来计算这个图。
任何不占用大量时间/内存的预处理都会被占用。最简单的想法是重新计算流程。另一个简单的想法是，保存之前的最大流量计算中使用的所有增加路径，现在为了添加顶点v，我们可以找到简单的路径(在上一步
浏览 0提问于2012-01-26得票数 10
回答已采纳
1回答
非赋权图中的最大流
、、、
最大流问题通常采用edmond-karp算法来解决，该算法建立残差图，并利用BFS来寻找增广路径。
但最大流问题通常是针对赋权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。
浏览 4提问于2017-02-22得票数 4
2回答
找到一条从a到b的简单路径，如果存在的话。(简单路径是没有重复顶点的路径。)如果我将顶点b设置为接收器，我不能确定它是否会包括v。如果我将v设置为接收器，当达到v时如何继续？
浏览 0提问于2012-01-05得票数 8
2回答
最大二部匹配方法中的误差
、、、
我想找出从源头到下沉的最大流量。一种方法是使用Fulkerson算法求解最大流问题，该算法适用于所有的图。我找到了一种简单的方法来找到最大流(太简单了，不正确！)我无法在这个方法中发现任何错误。最大流将是这两个数字的最小值，即min(c1，c2).Since --任何路径都需要从输出顶点列表中提取一个顶点，而从传入顶点列表中需要另一个顶点。
任何帮助都将不胜感激。
浏览 3提问于2016-01-24得票数 0
回答已采纳
1回答
我读过很多文章，指出用最大流算法可以找到二部图的最大匹配。但是，我们从最大流得到的匹配可能不是最大的，或者匹配没有最大的边。来自Anti Laaksonen的竞争性方案编制手册的例子：
但是，如果我以不同的方式呈现这个图，那么现在的图形是：
然后，随着最大流量算法的推进，匹配结果为1-5，2-7。因为1简单地擦除了通向水槽的路径，但是如果它被移到边缘1-6，那么匹配可能是
1
浏览 3提问于2021-06-24得票数 1
回答已采纳
在下面的最大流问题中，算法首先可以选择S-A-D-T路径。在这种情况下，算法将不再看到任何增强路径，因此它将生成4作为最大流的答案。但是，如果算法首先选择任何其他路径，则会看到最大流变为5。
浏览 11提问于2021-12-04得票数 0
1回答
我很难理解某些逻辑。我有一个二部图如下所示。我希望找到最优匹配的所有顶点在左侧(Viz，A1，A2，A3，A4)。我从朋友那里得到了一个建议，那就是边权之和可以用来解决这个问题。不过，我不知道，在这种情况下，边权之和会有什么帮助。例如，对于A1，我可以说AL2是最好的匹配，依此类推。然而，我的朋友建议，边缘权重是这个问题的最优解决方案。我无法理解如何才能成为最佳解决方案。他的想法是，所有的(A1，A2，A3，A4)都将连接到所有的(AL1，AL2，.，AL6)，对于每个边，我们将计算边权的总和。有人能帮我理解他的真正意思吗？
编辑:我认为这可能不是二分图中完美匹配的情况，因为左边的
浏览 5提问于2013-09-19得票数 0
回答已采纳
2回答
因此，我想问您，哪个包具有最简单的学习曲线，并且满足以下要求：
试图在两个顶点之间画出多条边，这样它们就不会重叠。(不需要任何图算法，如链接分析、最短路径、最大流等，但如果存在，则很好)
浏览 2提问于2011-04-04得票数 5
回答已采纳
在最大流问题中，当我应用ford-fulkerson算法寻找最大流时，如果图的所有链接都有权重1，则最大流将是我在ford fulkerson算法中找到的路径数，对吗？我是说，dfs路径的数目。
浏览 4提问于2014-04-17得票数 1
回答已采纳
2回答
全对最大流
、、
给定有向加权图，如何求出所有顶点对之间的最大流(或最小边切)。
天真的方法是简单地为每对调用一个像Dinic这样的最大流算法，其复杂性是O((V^2)*E)。
浏览 4提问于2012-12-21得票数 8
1回答
我被要求为以下问题开发一个算法：A流网络G，其边的最大容量为1G的最大流f_x_xa正整数K_。，如果K大于或等于max，删除所有穿过G的最小割集的边，如果K仍然大于零，删除随机边，并且新的最大流是零如果K小于，则删除与G最小割集相关的边的K，且新的最大流为delete 。我需要一些验证，因为最大流量/Min削减是新的我。最
浏览 0提问于2020-06-21得票数 0
回答已采纳
我不知道该用什么术语来搜索(我已经搜索过“映射算法”和“一对一算法”)，我想不出一个更简单(更规范)的公式。A B C D EL M N O PB --> MD --> N什么是最简单和/或最快的算法，它可以告诉地图的一个一对一的“子集”是否可以覆盖所有的项目“蛮力”算法很明显--稍微改进的是深
浏览 9提问于2013-01-22得票数 2
回答已采纳
1回答
我需要在这个网络中找到最大流量。这部分是一般的最大流量.然而，在这个特殊版本的最大流问题中，两个目标必须得到相同的流量。
有人能帮我吗?我该怎么做？
浏览 6提问于2014-01-21得票数 6
回答已采纳
我有一个无向图，想要计算两个顶点之间可能的最长路径，其中每条边只能访问一次，但每个顶点可以访问多次。
浏览 5提问于2021-10-29得票数 1
嗨，我很难用学习福特-富尔克森算法.然而，看到视频，这让我很困惑。这位讲师说，根据福特-富尔克森算法，最大流量为19，但我无法用19的费用找到任何削减。怎么了？
浏览 2提问于2018-12-02得票数 3
回答已采纳
1回答
我正在阅读Robert Sedgewick的算法第二卷。这一部分来自网络流量算法。流分解定理:任何循环都可以表示为沿一组至多E方向的边的流。推论1:任何st-网络都有一个最大流，使得由非零值诱导的子图是无圈的。
推论2:任何st-网络都有一个最大流，它可以表示为从s到t的至多E条有向路径的流。请用一个简单的例子帮助我理解上面的定理和推论，谢谢！
浏览 3提问于2012-05-14得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
