algorithm - 合并两个全局刚性图

Question

这是一道关于解决图论问题的算法的问题。

假设我们有两个通用的全局刚性图 F1 和 F2。我们还有一个连接顶点对 (i,j) 的边列表 E，其中 i 始终是 F1 中的一个顶点，j 始终是 F2 中的一个顶点。埃伦等人。 (见下面的引文)证明，在二维中，如果满足以下两个条件，则通过合并 F1、F2 和 E 创建的图 F 也一般是全局刚性的:

1. E 在 F1 中至少包含三个不同的顶点，在 F2 中至少包含三个不同的顶点。
2. E 中至少有 4 条边。

对于任何给定的 F1、F2 和 E，检查上述两个条件是否成立相对简单。我感兴趣的是为不满足上述条件的情况提供修复。具体来说，我正在寻找一种算法来找到最小的一组新边 E'，当与 E 合并时，它满足上述条件。有人知道我应该如何去做吗？

我试了一下这个问题，我知道如何检查 F1 和 F2 是否满足条件 (1)。然后我可以从每个图中随机选择新顶点以用于 E+E'。我坚持的是如何决定新旧顶点之间的连通性。

引文(Eren 等人)http://www.cs.columbia.edu/techreports/cucs-022-05.pdf

Answer 1

我认为你应该能够

• 选择一些任意的顶点集 V1 和 V2(当然不属于 E 中的任何边)直到我们有足够的满足(1)
• 将 V1 和 V2 的元素配对以在 E' 中形成边，直到用尽一组
• 将余数连接到相反集合中的任意顶点
• 如果 E+E' 仍然不满足 (2)，则在 F1 和 F2 之间再插入一条任意边