我有一个连通图 G，由列表列表定义，其中 G[n] 是 n 连接到的所有节点。我想找出可以删除多少条边，以便每个顶点都连接到另一个顶点。
例如：G = [[1], [0, 2, 4], [1, 3], [2], [1, 3, 5, 6], [4], [4]]
我们可以删除 3 条边 (1,2)、(1,4) 和 (4,3)
我找到了一种解决方案，我可以检查边缘的每种组合并找到最小的组合，以便满足我们的标准。我想找到一种更快、更有效的方法来做到这一点。
图中每个节点至少接触一条边的一组边称为图的边覆盖。你的问题相当于找到原始图的最小边覆盖；一旦你有了它，删除所有其他边缘就会给你答案。
好消息是，找到图中最小边覆盖的问题可以在多项式时间内解决。基本思想是首先在图中找到最大匹配（一组边，其中没有两条边共享端点），然后添加额外的边以覆盖剩余的未覆盖节点。用于查找图的最大匹配的多项式时间算法自 20 世纪 60 年代以来就已为人所知，但编写代码并不容易，因此您最好的选择可能是找到一个提供对此类算法的访问的现有软件包。