給定一個無向圖G =（V，E），確定G是否是一個完整的圖

Question

我很確定這個問題是P而不是NP，但我很難找出一個多項式約束算法來解決它。

Answer 1

您可以：

1. 檢查圖中的這個數字邊的是n(n-1)/2。
2. 檢查每個頂點是否連接到不同的頂點。

這將運行在O(V²)，這是多項式。

希望它有幫助。

Answer 2

這裏是一個O（E）算法：

1. 使用O（E），因爲它是輸入時間，掃描圖
2. 同時，記錄每個頂點P的程度，增加學位只有當鄰居不是p本身（自連接邊緣）和不是頂點q其中p和q已經有另一個邊已經計算過（多邊），這些檢查可以在O（1）中完成
3. 檢查是否所有頂點的度數是| V | -1，這一步是O（V），如果是的話那麼它是一個完整的gra pH值

共爲O（E）

Answer 3

下面是一個O（| E |）算法，它也有一個小常量。

枚舉完整圖中的每條邊是很平凡的。所以你所要做的就是掃描你的邊界列表，並確認每個邊緣都存在。對於每個邊（i，j），令f（i，j）= i * | V | + j。假設頂點編號爲0到| V | -1。

令bitvec是一個長度爲| V |的位向量， ，初始化爲0。

對於每個邊（i，j）中，設置bitvec[f(i, j)] = 1

G是一個完全圖，當且僅當bitvec ==的每個元件1

該算法不僅觸及E一次，而且如果有分散指令，它也是完全可以向量化的。這也意味着並行化是微不足道的。