O(m+n) 时间内的多图缩减

Question

考虑一个多重图 G，其中需要进行以下三个归约：

1. 从图中删除具有两个邻居的顶点，并且它们的邻居通过新边相互连接。
2. 从图中删除具有一个邻居的顶点。
3. 已从图中删除重复边。

这是我最近作业中的一道作业题，要求我证明这三个归约可以在 O(m+n) 时间内完成。非常感谢任何有助于更好地理解如何去做的帮助。谢谢！

Answer 1

这种缩减不是唯一的：考虑一个有两个顶点和一条边的图 v-w，它有两种可能的缩减。我将解释如何获得任意有效减少。

您首先要删除重复边：这可以在 O(n+m) 时间内使用集合或 hash-table 识别重复边来完成。我假设您将图形存储为从顶点到它们的邻接集的字典。

在此之后，您需要遍历顶点，并保留一个集合（或任何具有 O(1) 成员资格测试的容器）来存储 'to be deleted' 个顶点。在第一次传递顶点之后，这将包含任何度数为 1 或 2 的顶点。

现在，当您的 'to be deleted' 集合不为空时，您将：

• 从集合中弹出一个顶点 v。
• 如果v的度数为0，忽略它。
• 如果 v 的度数为 1 且其邻居为 w，请从您的图表中删除 v，并从 w's 邻接集中删除 v。如果 w 现在的度数为 1 或 2 并且不在 'to be deleted' 集合中，则将其添加到集合中。

否则，v 的度数 2 和两个不同的邻居 u, w。

• 如果u和w不相邻：添加一条从u到w的边，移除v及其图形的边缘。

• 如果 u 和 w 相邻：从图形中删除 v 及其边。如果 u 或 w 现在的学位为 1 或 2，请将它们添加到 'to be deleted' 集合。

这对每个顶点和边进行恒定的工作，但依赖于 'adjacency sets' 的特定图形表示，其中可以在恒定时间内删除边。在给定邻接列表或边列表的情况下，可以在 O(m+n) 时间内完成此表示的转换。