如何在图中找到每对与另一对至少相隔两条边的连接边对的最大数量？
How to find maximum number of such pairs of connected edges in a graph that each pair is separated from another pair by at least two edges?
我需要找到图形中连接边对的最大数量，以便每对与其他对至少由两条边分开。这可以看作是最大匹配，没有覆盖所有边缘的约束，其中交替路径中的每个组件的长度为 2.
术语说明：
连通对：边对必须在同一个连通分量中。
连通对：两条成对的边不一定需要共享一个顶点。
每对被至少两条边分开：给定对[(u1, v1) , (u2, v2)] 和 [(u3, v3), (u4, v4)], u ∈ {u之间的最小距离]1, v1, u2, v2} 和 v ∈ {u3, v3, u4, v4} 不少于两个？
每个对被至少两条边分开：给定对[(u1,v1), (u2, v2)] 和 [(u3, v3), (u4, v4)], 最小值u1 和 u2 之间的距离可以是任何值，包括零（同一顶点）?
最直接的方法是创建一个新图 G'，其中 G' 中的每对连接边都有一个顶点，并且边连接 G' 中的两个顶点，只要相应的边对G 相距小于 2 条边。然后，您可以在 G'.
中查找 maximum independent set
这远非理想，因为 G' 会很大并且独立集是 NP 完全的。如果你能证明 G' 有一些特殊的结构，你可能会做得更好。例如，如果它必然是二分的，那么 König's theorem 将让您使用最大匹配在多项式时间内找到最大独立集。 （这在实践中仍然会很慢，因为可能有 O(m^2) 个顶点...）
我需要找到图形中连接边对的最大数量，以便每对与其他对至少由两条边分开。这可以看作是最大匹配，没有覆盖所有边缘的约束，其中交替路径中的每个组件的长度为 2.
术语说明：
连通对：边对必须在同一个连通分量中。
连通对：两条成对的边不一定需要共享一个顶点。
每对被至少两条边分开：给定对[(u1, v1) , (u2, v2)] 和 [(u3, v3), (u4, v4)], u ∈ {u之间的最小距离]1, v1, u2, v2} 和 v ∈ {u3, v3, u4, v4} 不少于两个？
每个对被至少两条边分开：给定对[(u1,v1), (u2, v2)] 和 [(u3, v3), (u4, v4)], 最小值u1 和 u2 之间的距离可以是任何值，包括零（同一顶点）?
最直接的方法是创建一个新图 G'，其中 G' 中的每对连接边都有一个顶点，并且边连接 G' 中的两个顶点，只要相应的边对G 相距小于 2 条边。然后，您可以在 G'.
中查找 maximum independent set这远非理想，因为 G' 会很大并且独立集是 NP 完全的。如果你能证明 G' 有一些特殊的结构，你可能会做得更好。例如，如果它必然是二分的，那么 König's theorem 将让您使用最大匹配在多项式时间内找到最大独立集。 （这在实践中仍然会很慢，因为可能有 O(m^2) 个顶点...）