问题标签 [max-flow]

我了解残差图是什么。但是水平图是什么意思呢？ http://en.wikipedia.org/wiki/Dinic%27s_algorithm

我试图解决的问题如下：

给定一个有向图，找到“覆盖”整个图的最小路径数。多条路径可能经过同一个顶点，但路径的并集应该是所有路径。

对于给定的示例图（见图），结果应该是 2（1->2->4，并且 1->2->3 就足够了）。

通过分割顶点并为连接入顶点和出顶点的每条边分配 1 的下限，并将源链接到每个入顶点，将每个出顶点链接到接收器（它们没有显示在图，因为它会使整个事情变得混乱），现在的问题是在图中找到具有下限约束的最小流量。

但是，我已经读过，为了解决这个问题，我必须找到一个可行的流程，然后按如下方式分配容量：C(e) = F(e) - L(e)。但是，通过给每条Source-vertex edge、vertex-Sink edge、In-Out edge分配一个flow为1，可行的flow是正确的，总的flow等于vertices的个数。但是通过分配新容量，进出边（标记为蓝色）的容量为 0（它们的下限为 1，在我们选择可行流时，它们的流为 1），并且没有流量是可能的。

图 2：我如何选择“可行流程”

但是，从图中您可以清楚地看到，您可以引导一个满足每个“顶点边缘”下限的 2 流。

我是否理解错误的最小流量算法？哪里错了？！

网络中可以有多个最小切割。例如：

有四个最小切割，Ford-Fulkerson 找到一个“更接近” s（源）。我们可以对所有网络都说同样的话吗？也就是说，Ford-Fulkerson 找到离源最近的切口？如果为真，我们如何将流网络中“最接近源”的概念形式化？

我有一个Flow 网络。每条边都有capacity = 1.

我必须在最短的时间内将所有的东西从那里运送S到那里。T有没有办法将经典的最大流量问题简化为时间标准版本？

我一直在寻找给定问题的答案。提供的其他详细信息是：给定图中容量>0 的每个链接是p，容量<0 的链接的概率是1-p。像 {1,2,3,4} 这样的数据向量从节点 1 成功传输到节点 5 的概率是多少。

我知道这类问题有最大流的概念，但我仍然不明白通过这样的网络成功传输的概率。

第二个问题：在开始寻找最大流概念之前。我开始考虑给定一个起始节点和目标节点，可以简单地做一个 BFS 来找出从源节点到目标节点的许多可能路径并继续点击它们（我意识到如果有无限的路径，它就会变成指数时间具有巨大空间复杂度的算法，但说它是一个相当有限的网络）。那么为了调用P（成功传输）可以通过以下方式接近吗？

假设从节点 1 到节点 5 的路径数为 4，则 P（节点 1 和节点 5 之间的成功传输为）= P（路径 1）+ p（路径 2）+ p（路径 3）+ p（路径 4）-p（路径交叉点） ） 在哪里，

P(intersections) 是两个或多个路径可能共享边的概率，例如： p(intersections)=p(4c2)+p(4c3)-p(4c4) where 4cr--> no of no of path where r<= 4.

还有 p(path#)=p^no 该路径中的边数。我的做法对吗？另外，如果可以这样想，我怎样才能将其扩展到无限路径的可能性？

任何帮助或指示将不胜感激！谢谢你。

我需要帮助来了解如何解决以下问题：

亚当教授有两个孩子，不幸的是，他们彼此不喜欢。问题是如此严重，以至于他们不仅拒绝一起步行上学，而且实际上每个人都拒绝在其他孩子当天踩过的任何街区上行走。孩子们在拐角处交叉的道路没有问题。幸运的是，教授的房子和学校都在拐角处，但除此之外，教授不确定是否可以将两个孩子送到同一所学校。教授有一张城镇地图。展示如何将确定两个孩子是否可以上同一所学校的问题表述为最大流量问题。

我唯一能想到的就是有一个四角图。左上角的顶点代表源（亚当的房子），右下角代表汇（学校）。右上角x的角代表邻域中的角，而y代表邻域的左下角。因此，我们有从S -> C1、S -> C2、C1 -> t和出发的路径C2 -> t。每条路径的权重为 1，因为它只能容纳一个孩子。该图的最大流量为 2，证明他们可以上同一所学校。

我遇到的问题是我不确定我找到的这个解决方案是否能解决问题。最让我难过的部分是我不确定这意味着什么：但事实上，每个人都拒绝在其他孩子那天踩过的任何街区上行走。如果两个人都住在同一个街区的同一个房子里，这句话怎么能说得通呢？

我正在尝试在 Boost-graph 库的算法中使用具有捆绑属性的命名参数。edmonds_karp_max_flow

为了说明我的问题，我采用了现有的edmonds-karp 示例并将内部属性转换为捆绑属性（我将我的属性称为edge_t和node_t），并将命名参数转换为非命名参数。

这是编译良好的非命名参数版本：

这是不编译并触发大量模板错误的命名参数版本：

完整edmonds-karp-eg_modified.cpp来源：

以下是返回的错误：http: //pastebin.com/Vra8ZWHG。

它适用于非命名参数......但不适用于命名参数。

更新：有人似乎有完全相同的问题：svn.boost.org/trac/boost/ticket/8791。他使用Boost 1.50而不是修复它1.55。

• 升压图版本：1.58.0
• 编译器：g++ 5.0

我有一个有向图

首先，我使用了 Ford-Fulkerson 算法来增加网络的流量。当我标记顶点时，我看到路径上的流：s->a->b->d->t可以增加一个，因此图形更改为：

我知道在搜索最大流量时，您需要将连接最小切割和图形外部部分的边的所有容量相加。我的最小切割包含 vertices: s, a, c，所以当我将所有边加起来时c(G, !G) = 3 + 2 +2 + 1，这比 flow to t5 要大得多。

我做错了什么，我搞砸了FF还是最小化了？

Ford-fulkerson 算法确实适用于稍微修改的双向边缘。但我对 dinic 的算法感到困惑。这个算法是否也适用于双向边缘？

我目前正在编写一个将学生映射到课程的程序。目前，我正在使用 SAT-Solver，但我正在尝试实现一个多项式时间/非贪婪算法来解决以下子问题：

• 有学生（50-150）
• 有科目（10-20），例如“数学”、“生物学”、“艺术”
• 每个科目有课程（至少一门），例如'math-1'、'math-2'、'biology-1'、'art-1'、'art-2'、'art-3'
• 学生选择一些（固定）科目（10-12），并且对于每个科目，学生必须被分配到现有课程中的一门（如果可能）。选择“math-1”或“math-2”这门课程并不重要。
• 课程有最大允许学生人数（20-34）
• 每门课程都在一个固定的块中（= 时隙 1 到 13）
• 不得将学生分配到同一块中的课程

我现在描述我到目前为止所做的事情。

(1) 忽略 course-student-limit

我能够用匈牙利算法/二分匹配解决这个问题。每个学生可以通过如下建模来单独计算：

• 左节点代表科目“数学”、“生物学”、“艺术”（学生的）
• 右节点代表块'1'，'2'，....'13'
• 为从“主题”到“块”的每门课程插入一条边

这样，学生被分配到每个科目的课程，而不参加同一块中的课程。但是 course-limits 被忽略了。

(2) 忽略学生选择的科目

我能够用最大流量算法解决这个问题。为每个学生建模以下内容：

• 第 1 层：从源到每个学生，流量为 13
• 第 2 层：从每个学生到他/她的个人区块，流量为 1
• 第 3 层：从每个学生块到该块中的每个课程，流程为 1
• 第 4 层：从每门课程到具有“最大学生限制”的接收器

这样，学生可以选择任意课程并且课程限制已满。但他/她可能不走运，被分配到'math-1'、'math-2'和'math-3'，忽略了'生物学'和'艺术'科目。

(3) 贪婪的匈牙利语

我的另一个想法是一次将一个学生与匈牙利算法匹配并调整权重，以便首选“更多空课程”。例如，可以建模：

• 左节点是学生的主题
• 右节点是块
• 为每门课程插入一条从主题到课程块的边，权重 = 空闲座位数

然后计算最大权重匹配。

我真的很感激任何建议/帮助。

谢谢！