今天我的算法測驗中的圖論問題，我想幫助理解

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個頂點。