在无向图中查找非相交2周期的最大数量

Question

我有一个adjecency矩阵和一个adjecency列表（我可以使用）都表示一个图。

基本上，我该如何在图中配对连接的顶点，以便剩下最不成对的（和断开的）顶点？

我已经尝试过这种蛮力策略：

def max_pairs(adj_matrix): 
    if len(adj_matrix) % 2: 
     # If there are an odd amount of vertices, add a disconnected vertex 
     adj_matrix = [adj + [0] for adj in adj_matrix] + [0] * (len(adj_matrix) + 1) 
    return max(adj_matrix) 

def all_pairs(adj_matrix): 
    # Adapted from http://stackoverflow.com/a/5360442/5754656 
    if len(adj_matrix) < 2: 
     yield 0 
     return 
    a = adj_matrix[0] 
    for i in range(1, len(adj_matrix)): 
     # Recursively get the next pairs from the list 
     for rest in all_pairs([ 
       adj[1:i] + adj[i+1:] for adj in adj_matrix[1:i] + adj_matrix[i+1:]]): 
      yield a[i] + rest # If vertex a and i are adjacent, add 1 to the total pairs 

这是不行了小图，但我一起工作的图表有多达100个顶点。

有没有一种方法来优化这个，以便它可以处理这么大的图？

这是另一个有算法的问题的代名词吗？我搜索了“大多数非交叉k周期”及其变体，但找不到算法来做到这一点。

Answer 1

有多项式时间解决方案（它在O(|V|^2 * |E|)工作）。它被称为Blossom algorithm。这个想法是在二分图中做类似匹配的事情，但也会将奇数长度的周期缩减为一个顶点。