找到最大號碼。圖的邊緣

無向圖有'n'個頂點和0個邊。我們可以繪製的最大邊數是什麼，這樣圖保持斷開。找到最大號碼。圖的邊緣

我已經做出瞭解決方案，我們可以排除一個頂點，並且可以找到無向圖的n-1頂點之間的最大邊數，以便圖仍然保持斷開狀態。這對於n個頂點是n（n-1）/ 2，對於n-1個頂點將是（n-1）（n-2）/ 2有沒有更好的解決方案？

2012-04-08 Luv

您的解決方案應該是最好的解決方案。

因爲添加的任何新邊必須在一端具有第n個頂點。

2012-04-08 10:35:58 sukunrt

提供的理由「」因爲添加了任何新邊緣必須在第一個頂點的第一個頂點「提供了爲什麼它是*局部最大值*而不是全局最大值*的解釋。這種解釋並不包含完全不同結構的解決方案，這些解決方案可能有更多的邊緣 - 沒有適當的證明，爲什麼他們不能。 – amit 2012-04-08 11:27:20

多圖的邊數顯然是無限的。現在，如果它不能有自循環，那麼你必須選擇兩個頂點來添加一個邊。您已完全連接了第（n-1）個頂點。要添加一個邊，兩個頂點都不能來自初始的n-1個頂點集，因爲您已經從初始的n-1個頂點創建了每個邊。所以其中一個邊緣必須是第n個邊緣。如果你有自循環允許，那麼你可以添加更多的邊緣，因爲自循環不會添加到連接。 – sukunrt 2012-04-08 12:09:22

這完全沒有涵蓋由兩個大小不等於1，n-1的完整子圖組成的圖的可能性。解決方案（意外）是正確的，但推理不是。 – voidengine 2012-04-08 12:53:51

如果圖可以有多條邊，那麼對於n> = 3，答案是無窮大。
如果它也可以包含自循環，答案是對n> = 2無窮大，

如果沒有那些握着你的解決方案是正確的。

來源

2012-04-08 10:56:32 kilotaras

您可以使用分析解決此問題。把你的想法和概括。您將n個頂點分成兩組，大小分別爲x和n-x。現在的邊數是x功能，通過

f(x)= x(x-1)/2 + (n-x)(n-x-1)/2 
    f(x) = 1/2(2x^2 - 2nx +n^2 - n)

充分發揮了這一功能是你想要的分區大小的值來表示。如果進行計算，則會發現它從x=0減少到x=n/2，然後增加到x=n。由於x = 0或x = n意味着收集圖表，您將採取下一個最大值x=1。所以你的直覺是最佳的。

來源

2012-04-08 11:18:11 UmNyobe

+1此解決方案證明了爲什麼給出的答案也是局部最大值。爲了完全覆蓋自己，你可能還想找到f''，並找出'f''（MIN）<0'，並且驗證f（n），f（0）不是可行解，並且驗證f（1），f（n-1） – amit 2012-04-08 11:34:09

@amit f'（x）= 4x - 2n ... – UmNyobe 2012-04-08 11:34:31

並且你正確的是f'' – UmNyobe 2012-04-08 11:35:08

找到最大號碼。圖的邊緣

回答

相關問題