我需要帮助来了解如何解决以下问题：
亚当教授有两个孩子，不幸的是，他们彼此不喜欢。问题是如此严重，以至于他们不仅拒绝一起步行上学，而且实际上每个人都拒绝在其他孩子当天踩过的任何街区上行走。孩子们在拐角处交叉的道路没有问题。幸运的是，教授的房子和学校都在拐角处，但除此之外，教授不确定是否可以将两个孩子送到同一所学校。教授有一张城镇地图。展示如何将确定两个孩子是否可以上同一所学校的问题表述为最大流量问题。
我唯一能想到的就是有一个四角图。左上角的顶点代表源（亚当的房子），右下角代表汇（学校）。右上角x的角代表邻域中的角，而y代表邻域的左下角。因此，我们有从S -> C1、S -> C2、C1 -> t和出发的路径C2 -> t。每条路径的权重为 1，因为它只能容纳一个孩子。该图的最大流量为 2，证明他们可以上同一所学校。
我遇到的问题是我不确定我找到的这个解决方案是否能解决问题。最让我难过的部分是我不确定这意味着什么：但事实上，每个人都拒绝在其他孩子那天踩过的任何街区上行走。如果两个人都住在同一个街区的同一个房子里，这句话怎么能说得通呢？
更新：原来，我误读了这个问题。问题要求找到“边缘不相交”的路径，而不是顶点不相交的路径。在这种情况下，解决方案只是将每个角表示为一个顶点，将每个块表示为容量为 1 的边，并运行常规的最大流（如下面的 Curious 正确建议的那样）。
我相信 OP 有同样的困惑，基于
但事实上，每个人都拒绝在其他孩子那天踩过的任何街区上行走。如果两个人都住在同一个街区的同一个房子里，这句话怎么能说得通呢？
请注意，孩子们住在同一个角落的同一个房子里，而不是同一个街区。
如果有一天有人真的在寻找顶点不相交问题，我会留下其余的答案：
如果我正确理解了这个问题，它要求的是找到从源到接收器的两条顶点不相交的路径。仅按原样使用图形，并为每条边分配容量1是不够的。考虑以下示例：
s -> C1, C1 -> C3, C3 -> C4, C4 -> t
s -> C2, C2 -> C3, C3 -> C5, C5 -> t
如果您1为这些边中的每一个分配容量，并运行任何最大流量算法，它将找到最大流量 2，但没有两条顶点不相交的路径（两条路径都将通过 vertex C3）。
要解决它，您需要调整图表。s对于除和之外的每个顶点t，将其一分为二。说顶点u被分成u'和u''。使所有要进入的边u进入u'，而所有来自的边都进入u（u''这些边的容量无关紧要，只要它是正的，因此您可以将其设置为1）。最后，用容量从u'到添加一条边，并在该图上运行最大流量。由于我们在分割节点之间添加了这些边，每个顶点最多只能使用一次，因为要使用的顶点我们需要从那里进入、从到、从那里退出，并且只有一个流单元可以从到u''1u'u'u''u'u''.
让我们保持简单.. 首先要做的事情。为什么你只限制在他的房子和学校以外的两个角落。在问题中没有这样提到。
亚当问题的建模可以像这样
顶点：城镇的各个角落
有向边 ：在两个方向上连接拐角的所有道路，即如果我们有 2 个拐角 p,q 那么我们将有从 p 到 q 以及从 q 到 p 的边
对于所有边 (u,v) ，c(u,v)=1
现在解决最大流量问题，如果是>= 2，Adam 是幸运的。
我从未听说过最大流量问题，所以这是我从维基百科收集到的。
似乎该图(V,E)应该为每个街道交叉点有一个顶点，每个街道（交叉口之间）应该有一个边。然后每条边的容量为 1（如你所说）。当然，如果其中一个孩子到了学校，他们也可以回家（使用“对面图”中所有边都颠倒的类似路径）。
那么唯一的歧义是：边缘的直接应该是什么？如果图形不必定向，这可以作为问题的表述。
由于问题指定房屋（s）和学校（t）都在拐角处，我假设拐角不计为“在街区上行走”并且问题说他们在拐角处穿越路径没有问题，所以例如，他们可以一起过马路到另一个街区，只要他们中的一个人走人行道到另一个角落，另一个立即过马路到另一个街区。
在这种情况下，流程中的限制因素是块，因此它们必须成为容量为 1 的流程图中的边。但是它们连接什么？它们必须连接到其他块。所以想象一个由 9 个方块组成的正方形：
1 2 3
4 5 6
7 8 9
房子在1的东南角，学校在5的东南角。两个孩子都可以过马路到5号街区，但只有一个人可以绕过5号街区才能到对面拐角的学校。另一个也可以穿过 4 号街区，然后到 7 号街区，然后到 8 号街区，在那里他可以过马路到 5 号街区拐角处的学校。
所以房子可以到达第 1、2、4 和 5 号街区。学校可以从 5、6、8 或 9 号到达。我的第一个想法是将每个街区建模为两个节点，输入和输出，一个容量为 1 的边将输入连接到输出。其他节点将与容量至少为 2 的边链接。您还需要 s 和 t 的节点。将 s 链接到 1、2、4 和 5 的输入，将 5、6、8、9 的输出链接到 t。然后将块输出链接到您可以从角落到达的任何块的输入，即 1 的输出进入 2、4、5 的输入，2、4、5 的输出也进入 1 的输入。
一个更简单的想法可能是每个角是一个节点，连接到它周围的块的输入，而它周围的块的输出连接到角节点。所有的边都应该至少有两个容量，除了连接块输入和输出的容量为 1。这样限制因素是“在块上行走”。只要最后的流量为2，他们就可以做到。
所以让我们简化图表并去掉我们不会使用的块。一个孩子可以从 s 到 t 绕过第 5 街区，另一个可以过马路到 4，然后在拐角 a 穿过第 8 街区，然后沿着第 8 街区走到学校所在的拐角 t：
s
4 5
a t
8
这是边缘：
s->4in (capacity 2)
s->5in (capacity 2)
4in->4out (capacity 1) // limiter
5in->5out (capacity 1) // limiter
8in->8out (capacity 1) // limiter
4out->s (capacity 2)
4out->a (capacity 2)
5out->s (capacity 2)
5out->a (capacity 2)
5out->t (capacity 2)
8out->a (capacity 2)
8out->t (capacity 2)
a->4in (capacity 2)
a->5in (capacity 2)
a->8in (capacity 2)
一个孩子的路径 s->5in->5out->t
其他孩子的路径 s->4in->4out->a->8in->8out->t
我也在寻找解决方案并找到了这个，它对我来说似乎是正确的。
这意味着另一个孩子不会走那条路去上学。现在，如果两个孩子都可以上学，这意味着从源（房子）到汇（学校）的流量至少为 2。同样，如果可以找到 G 中的最大积分流量s to t that has a value of at least 2, then both children can go to school. Otherwise, it won’t be possible."