今天我进行了本学期的算法测验，我无法弄清楚这两个问题，它们已经困扰了我一整天。我已经浏览了我的笔记和讲义，但我仍然不确定。如果有人能看一下并对这些问题提供一些见解，我将不胜感激。这些不是家庭作业，我已经参加了测验。
对或错问题
1) [释义] 具有 n 个顶点的二部图中的最大边数为 n(n-1)/2。
我把它记为 False，我的逻辑是 n 个顶点意味着我们有两个 n/2 行。第一个节点与第二行有 n/2 个连接，第二行与第二行有 n/2 个连接...等等...
因此，我计算出具有 n 个顶点的二部图中的最大边数为(n^2/4)。
2) [释义] 是否可以采取一种切割，即不一定是有向流图中的最小 st 切割（Ford-Fulkerson 算法），使得流量容量大于 st 切割容量？
我写了 false，但我不明白这个问题...是否可以采取 st 切割，使流量更大？我知道弱对偶定理和“最大流量=最小切割”，所以我写下了 false，但我不知道。
简答题：
1）解释测试图是否连通的有效方法。
我建议进行广度优先搜索，如果图中有 BFS 算法没有找到的节点，那么它就没有连接。我写下运行时间为 O(m+n)，因此这是一种有效的算法。这道题值两分，是最后一道题，但我现在担心这是一道刁钻题。
2）在图中：
列出证明最小顶点覆盖的顶点集[解释]
我的答案是{A , D}, {A, E}, {B, C}, {B, D}, {C, E}，但现在我担心只是 {A}, {B}, {C}, { D}、{E}...
感谢您花时间阅读！ :)
Today I had my algorithms quiz for the semester and I can't figure out these two questions and they've been bugging me all day. I've gone through my notes and the lecture notes and I'm still unsure. I would appreciate it if someone could take a look and provide some insight into these questions. These are not homework and I've already sat the quiz.
True or False questions
1) [Paraphrased] The maximum number of edges in a bipartite graph with n vertices is n(n-1)/2.
I put this down as False, my logic is that n verticies means we have two n/2 rows. The first node has n/2 connections to the second row, the second row has n/2 connections to the second row... etc...
Hence, I calculated the maximum number of edges in a bipartite graph with n vertices to be (n^2/4).
2) [Paraphrased] Is it possible to take a cut, that is not necessarily the minimum s-t cut in a graph with directed flows (Ford–Fulkerson algorithm) such that the flow capacity is greater than the s-t cut capacity?
I put down false, but I don't understand the question... Is it possible to take an s-t cut such that the flow capacity is greater? I know the weak duality theorem and 'max flow = min cut' so I put down false, but I have no idea.
Short answer question:
1) Explain an efficient way to test weather a graph is connected.
I suggested doing a breadth first search and if there were nodes that were not found by the BFS algorithm in the graph, then it was not connected. I wrote down the running time was O(m+n) hence it was an efficient algorithm to use. It was worth two marks and it was the final question but I'm now worried it was a trick question.
2) In the graph:
List the sets of vertices which demonstrate minimum vertex cover [paraphrased]
My answer was {A, D}, {A, E}, {B, C}, {B, D}, {C, E}, but now I'm worried it was just {A}, {B}, {C}, {D}, {E}...
Thanks for taking the time to read! :)
发布评论
评论（3）
我现在只有第一张图的答案，但你是对的。
在二分图中，必须有两组节点 - 例如第一组中的 x 和第二组中的 (n - x)。
该图中的最大边数将为 x(nx) 或 nx - x^2。
nx - x^2 的最大值为 x = (n/2)
因此图中的最大边数为 (n/2) * (n - (n/2)) = (n^2)/4 ，正如你所指出的。
I only have the answer to the first graph right now, but you are correct.
In a bipartite graph, there have to be two sets of nodes - say x in the first group and (n - x) in the second.
The maximum number of edges in this graph will then be x(n-x), or nx - x^2.
The maximum value of nx - x^2 is x = (n/2)
So the maximum number of edges in the graph is (n/2) * (n - (n/2)) = (n^2)/4, as you pointed out.
图连接性：
关于使用 BFS，你是对的。经过一次 BFS 迭代后，如果所有节点都被访问过，那么我们可以得出结论，该图是连通的。
或者，这也可以使用 DFS 来完成。方法保持不变。
Graph Connectivity:
You are right about using BFS. After one iteration of BFS, if all the nodes are visited then we can conclude that the graph is connected.
Alternatively, this can be also done using DFS. Approach remains the same.
1）已经回答了，我同意你是对的。
2）：正如所述，这个问题似乎含糊不清。
流通能力如何？全网的？或削减？
如果是后者，似乎是在问能否A>？ A、这显然是错误的。
如果是前者，那么很明显答案是错误的。如果可以找到这样的切割，那么 max-flow=min-cut 就不会成立：网络的最大流量将大于 st 切割的最小容量。
然而，可以采取这样的切割，使得切割的流量大于网络的最小第一切割容量。您你不认为他们就是这个意思吗？例如，在本文顶部的示例中，如果您在 s 和其余部分之间进行剪切网络的切割容量大于网络的最小st切割容量。
但即使这样的解释似乎也不太可能，因为它相当微不足道……“最小值”的含义是可能存在更大的值。
也许看到确切的原始措辞会有所帮助。
简短回答：
1）已经得到回答，虽然我不明白 m 是什么（在 O(m+n) 中），除非你在谈论二部图？
2）我同意@glebm的观点，你搞错了......抱歉。 “图的顶点覆盖是一组顶点”，但您似乎已经写了一个列表边缘？接下来是单例顶点集列表？
由于这是一个完整的图，因此所有顶点都是可以互换的。因此，我们并不真正关心哪个顶点，而只关心需要多少顶点才能触及所有边。答案并不难找到。如果我们选择任意三个顶点，则连接其他两个顶点的边不会被“覆盖”。量子电子器件。
事实上我们可以证明，对于任意n个顶点的完全图，最小顶点覆盖需要n-1个顶点。
1) has been answered, and I agree that you were right.
2): The question seems ambiguous as stated.
the flow capacity of what? of the whole network? or of the cut?
If the latter, it seems to be asking can A > A, which is obviously false.
If the former, again it's clear that the answer is false. If it were possible to find such a cut, then max-flow=min-cut would not be true: the max flow of the network would be greater than the minimum capacity of an s-t cut.
However it is possible to take a cut such that the flow capacity of the cut is greater than the minimum s-t cut capacity of the network. You don't suppose that's what they meant? For example, in the example at the top of this article, if you cut between s and the rest of the network, the capacity of the cut is greater than the minimum s-t cut capacity of the network.
But even that interpretation seems unlikely because it's pretty trivial... the implication of a "minimum" is that there may be greater values.
Maybe it would help to see the exact original wording.
Short answer:
1) has been answered, although I don't understand what m is (in O(m+n)), unless you're talking about a bipartite graph?
2) I agree with @glebm that you got it wrong... sorry. "Vertex cover of a graph is a set of vertices", but you seem to have written a list of edges? followed by a list of singleton sets of vertices?
Since this is a complete graph, all vertices are interchangeable. So we don't really care which vertices, but only how many vertices we need in order to touch all the edges. The answer is not hard to find. If we pick any three vertices, the edge connecting the other two vertices is not "covered". QED.
In fact we can prove that for any complete graph of n vertices, the minimum vertex cover requires n-1 vertices.