生成算法來確定如果一個圖與給定的算法創建

Question

令： ģ - 圖形 V（G） - 的頂點 E（G） - 的邊緣 V，W特定頂點。

算法構建圖：

//adding v (a new vertex to the graph) 
if v has a friend in V (G) then E ← E ∪ {vw|w ∈ V (G)} 
G ← (V ∪ v,E) 

能否請你給我至少線索，我怎麼能找到一個給定的圖形與此算法生成？

預先感謝您。

Answer 1

如果G的頂點數爲0，則必須在添加最後一個「友好」頂點後添加頂點。刪除它們。一旦我們完成剔除無朋友，就必須有一個「最後友好的頂點添加」，因爲它附着在一切事物上，因此可以識別。找到它，刪除它，然後回到尋找和摧毀無朋友。如果圖形最終被這個過程完全破壞，它可以通過你的算法創建。

Answer 2

這幾乎可以說，當您將v添加到圖中時，如果在圖中有任何朋友，則它會獲得所有現有頂點的邊。所以每個添加或者不添加邊，或者邊添加到所有頂點。

棘手的是，沒有任何朋友添加的頂點仍可能從後續添加的頂點獲得邊緣。如果您可以知道它們添加的順序，那麼您可以通過重播該順序並檢查每個添加是否添加0或所有可能的邊來確定圖形是否可行。

如果您不知道該順序，可以嘗試通過移除最近的頂點來「解開」圖形，如果能夠找出它們。

編輯建議的算法刪除，因爲它的功課;-)。