通过操作将一个图转换为另一个图

Question

伙计们！我遇到了 3-4 天前看到的一个图表问题。它来自 2004 年特维尔举行的俄罗斯信息学奥林匹克公开赛。给你两张图表。每个图由 N 个节点和 M 个边组成。你需要将第一张图变成第二张图，或者说这是不可能的。您只能使用以下操作：

1. 选择 4 个不同的节点，它们 2×2 连接（我们称它们为 v1、v2、v3 和 v4 - v1 和 v2 连接，v3 和 v4 连接）
2. 移除连接每对的这 2 条边并通过任何其他方式连接它们： 2.1 v1 与 v3 ； v2 与 v4 2.2 v1 与 v4 ； v2 与 v3 您最多可以使用 48000 个这样的操作。 这是一个链接：https://informatics.msk.ru/mod/statements/view.php?chapterid=1054#1

我尝试寻找某种算法或以下操作的某种联系，但没有成功。我也尝试创建自己的示例并尝试解决它们，但我找不到任何模式。

Answer 1

假设两个图中的顶点之间存在 1:1 对应关系，即图 1 中标记为 V 的顶点与图 2 中标记为 V 的顶点“相同”。

• 循环图1中的每4组顶点
  • 如果顶点没有连接
    • 继续
  • 如果组中的顶点连接不能转换为图2相同顶点的顶点连接。
    • 继续
  • 变换
  • 如果 2 个图相同
    • 成功
• 端循环
• 失败