在無向圖中查找非相交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。這個想法是在二分圖中做類似匹配的事情，但也會將奇數長度的週期縮減爲一個頂點。