在无向图中找到最大数量的非相交 2-cycles

Question

我有一个邻接矩阵和一个邻接列表（我都可以使用），它们都表示一个图。

基本上，我如何配对图中的连接顶点，以便留下最少未配对（和断开连接）的顶点？

我试过这个蛮力策略：

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 
    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 个顶点。

有没有办法优化它以便它可以处理那么大的图？

这是另一个有算法的问题的同义词吗？我搜索了 "Most non-intersecting k-cycles" 及其变体，但找不到执行此操作的算法。

Answer 1

有多项式时间解（在O(|V|^2 * |E|)有效）。它被称为 Blossom algorithm。这个想法是做一些类似于二部图中的匹配的事情，但也将奇数长度的循环收缩到一个顶点。

在无向图中找到最大数量的非相交 2-cycles

Find the maximum amount of non-intersecting 2-cycles in an undirected graph

python

algorithm

optimization

graph-theory