未連接圖中的最大邊數

Question

在具有n頂點且無邊的無向圖中，可添加的邊的最大數量是多少以便圖保持不連接？這是一個面試問題。

1. NC2
2. （N-1）C2
3. N！
4. （N-1）！

Answer 1

B（N-1）C2

這樣的曲線圖的一個例子是n-1個頂點和一個分離的頂點的一個完整的曲線圖。

在這個例子中，補圖有nC2-（n-1）C2 = n-1條邊。 並連接給定的圖表或其補碼（proof）。因此，如果我們構建一個具有多於（n-1）個C2邊的圖，那麼補碼將具有小於n-1個邊並且不能被連接，因此我們的圖將是。

Answer 2

具有N個頂點的圖形中的最大邊數是NC2（link）。

請注意，要保持未連接狀態，其中一個頂點不應有任何邊緣。更正式的說，必須有a cut（其間不會有任何邊），一邊只有一個頂點。爲什麼不多於一個頂點？通過感應證明：

0,1和2個頂點的情況很簡單。

考慮一個有3個頂點的圖。最好的切割將是一邊有2個頂點，另一邊有1個頂點。

現在假設最佳切割是一邊有N-1個頂點，另一邊有一個頂點，N> = 3。現在嘗試添加一個頂點。將頂點添加到具有一個頂點的邊將導致可以添加的一條邊。將頂點添加到另一側會導致N-1個可能的邊緣。當N> = 3時顯然N-1> 1。因此，最好將頂點添加到具有N-1個頂點的邊上。

現在有兩種方法從這裏去：

1. 考慮圖形沒有邊緣之一。此子圖的最大邊數爲(N-1)C2。

2. 考慮圖的邊緣的最大數量，並從一個頂點減去邊的數量。這給出NC2 - (N-1) = N(N-1)/2 - 2(N-1)/2 = (N-2)(N-1)/2 = (N-1)C2。

因此，答案是(N-1)C2，即選項2.