让: G - 图形 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)
你能至少给我一个线索吗？我怎么才能知道给定的图是否是用这个算法构建的？
提前谢谢你。
最佳答案
如果 G 具有度数为 0 的顶点，则它们必须是在添加最后一个“友好”顶点之后添加的。删除它们。一旦我们完成剔除无友项，就必须有一个“添加的最后一个友好顶点”，可以识别，因为它附加到所有内容。找到它，移除它，然后返回寻找并摧毁无友。如果该图最终被此过程完全破坏，则可以通过您的算法创建它。
关于algorithm - 构建算法以确定是否使用给定算法创建图形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4261170/