今天我的算法测验中的图论问题，我想帮助理解

Question

今天我有我的算法测验的学期，我不知道这两个问题，他们一直在窃听我整天。我已经阅读了笔记和讲义，但我仍然不确定。如果有人能够看一看这些问题并提供一些见解，我将不胜感激。这些不是作业，我已经参加了测验。

True或False问题

1）[意译]在二部图具有n个顶点的边的最大数量为n（n-1）/ 2。

我把这个假设为False，我的逻辑是n个节点意味着我们有两个n/2行。第一个节点与第二个行有n/2个连接，第二个行与第二个行有n/2个连接...等等...

因此，我计算了二分图中边的最大数目n个顶点为（n^2/4）。

2）[释义]是否有可能进行切割，这不一定是带有定向流的图形中的最小s-t切割（Ford-Fulkerson算法），使得流量大于s-t切割能力？

我放下假，但我不明白这个问题......是否有可能采取S-T切割，使流动能力更大？我知道弱对偶定理和'max flow = min cut'，所以我放弃了假，但我不知道。

短答案问题：

1）解释一个有效的方式来测试天气的曲线连接。

我建议做一个宽度优先的搜索，如果在图中没有找到BFS算法找到的节点，那么它就没有连接。我写下了运行时间为O（m + n），因此它是一种有效的算法。这是值得的两个分数，这是最后一个问题，但我现在担心这是一个诡计的问题。

2）在该图中：

列表其证明最小顶点覆盖的顶点集[转述]

我的回答是{A，d}，{A，E} ，{B，C}，{B，D}，{C，E}，但现在我担心它只是{A}，{B}，{C}，{D}，{E} ...

感谢您花时间阅读！ :)

Answer 1

我现在只有第一个图的答案，但你是正确的。

在一个二部图中，必须有两组节点 - 比如第一组中的x和第二组中的（n - x）。

此图中的最大边数为x（n-x）或nx - x^2。

NX的最大值 - X^2为x =（N/2）

所以边缘的曲线图中的最大数量是（N/2）*（N - （N/2）） =（n^2）/ 4，正如你所指出的那样。

Answer 2

图形连通性：

你是对的使用BFS。在BFS的一次迭代之后，如果所有节点都被访问，那么我们可以得出结论，该图连接。

或者，也可以使用DFS完成此操作。方法依然如此。

Answer 3

1）已经回答，我同意你是对的。

2）：如上所述，这个问题似乎不明确。

such that the flow capacity is greater than the s-t cut capacity 

流量是什么？整个网络的？或削减？

如果是后者，似乎要求A> A，这显然是错误的。 如果前者，答案显然是错误的。如果有可能找到这样的切割，那么最大流量=最小切割将不是真的：网络的最大流量将大于s-t切割的最小流量。

然而是可能采取的切割使得切割的流动容量比网络的最小 S-T切容量更大。你不认为这就是他们的意思？例如，在example at the top of this article中，如果您在s与网络的其余部分之间切换，则切割的容量大于网络的最小s-t切割容量。

但即使这种解释似乎不大可能，因为它是非常微不足道的......“最低”的含义是可能有更大的价值。

也许这将有助于看到确切的原始措辞。

简短的回答：

1）已回答了，虽然我不明白m是（在O（M + N）），除非你是在谈论一个二分图？

2）我同意@glebm，你说错了......对不起。 “图的Vertex cover是一组顶点”，但您似乎写了一个边的列表？接下来是一组单顶点顶点？

的曲线图的Vertex cover是顶点的一组 使得 图的每个边缘是入射到集的至少一个顶点 。

由于这是一个完整的图，所有的顶点都是可以互换的。所以我们并不在意哪个顶点，但只有我们需要多少个顶点才能触及所有的边。答案不难找到。如果我们选取任何三个顶点，则连接其他两个顶点的边不会被“覆盖”。 QED。

实际上，我们可以证明，对于任何n个顶点的完整图，最小顶点覆盖需要n-1个顶点。