networkx maximal_matching()不会返回最大匹配

Question

我正在学习使用Python模块networkx来进行二分图匹配。该模块中有两个函数可用于计算图的最大基数匹配：

1. nx.maximal_matching()
2. nx.bipartite.maxmum_matching()

请注意，尽管名称为maximal_matching，但其文档确实说明它“在图中查找最大基数匹配”。

由于我的图是二分图，我假设这两个函数会给出相同的结果，至少具有相同数量的边缘。然而，我的代码似乎表明nx.maximal_matching()给出了错误的答案：可以有一条额外的边缘，正如nx.bipartite.maxmum_matching()所建议的那样。

以下是我的工作代码：

import networkx as nx
from networkx import bipartite    

def plotGraph(graph,ax,title):    
    pos=[(ii[1],ii[0]) for ii in graph.nodes()]
    pos_dict=dict(zip(graph.nodes(),pos))
    nx.draw(graph,pos=pos_dict,ax=ax,with_labels=True)
    ax.set_title(title)
    return   

if __name__=='__main__':    
    #---------------Construct the graph---------------
    g=nx.Graph()
    edges=[
            [(1,0), (0,0)],
            [(1,0), (0,1)],
            [(1,0), (0,2)],
            [(1,1), (0,0)],
            [(1,2), (0,2)],
            [(1,2), (0,5)],
            [(1,3), (0,2)],
            [(1,3), (0,3)],
            [(1,4), (0,3)],
            [(1,5), (0,2)],
            [(1,5), (0,4)],
            [(1,5), (0,6)],
            [(1,6), (0,1)],
            [(1,6), (0,4)],
            [(1,6), (0,6)]
            ]

    for ii in edges:
        g.add_node(ii[0],bipartite=0)
        g.add_node(ii[1],bipartite=1)

    g.add_edges_from(edges)

    #---------------Use maximal_matching---------------
    match=nx.maximal_matching(g)    
    g_match=nx.Graph()
    for ii in match:
        g_match.add_edge(ii[0],ii[1])

    #----------Use bipartite.maximum_matching----------
    match2=bipartite.maximum_matching(g)    
    g_match2=nx.Graph()
    for kk,vv in match2.items():
        g_match2.add_edge(kk,vv)

    #-----------------------Plot-----------------------
    import matplotlib.pyplot as plt
    fig=plt.figure(figsize=(10,8))

    ax1=fig.add_subplot(2,2,1)
    plotGraph(g,ax1,'Graph')

    ax2=fig.add_subplot(2,2,2)
    plotGraph(g_match,ax2,'nx.maximal_matching()')

    ax3=fig.add_subplot(2,2,3)
    plotGraph(g_match2,ax3,'bipartite.maximum_matching()')

    plt.show()

这里是生成的图表。如图所示，subplot-2有6个边缘，而subplot-3有7个。这是networkx实现中的一个错误还是我在这里做错了什么？ PS：我的networkx版本是1.11。

- Jason

Answer 1

networkx.maximal_matching算法并不能按照您的意愿给出一个最大基数匹配。它实现了一种简单的贪心算法，其结果在纯粹意义上是最大的，因为无法添加任何其他边。

对于您想要的全局最大基数匹配，它的对应算法是networkx.max_weight_matching。

- donkopotamus

---

我明白了。我甚至没有查看max_weight_matching，因为我的图没有权重。谢谢你为我澄清这一点。 - Jason

我现在理解这两者之间的区别，但我想知道何时可以使用“最大匹配”？是否有问题的示例，仅查找最大匹配就足够了，而不一定是最大匹配？ - Bulat

Answer 2

根据此错误报告的答案，返回的匹配是最大匹配而非最优匹配。按照他们的术语（我不知道这有多常见），这意味着它提供的是局部最优解而非全局最优解。

因此，对于由maximal_matching返回的匹配，只保证通过添加边到该匹配中不能使其更大（同时仍然是匹配）。但是，并没有保证不存在具有更多边的匹配。

- FlorianK

Answer 3

在图论术语中，最大匹配和最大权匹配是不同的（即使在二分图中也是如此）。最大匹配仅意味着您无法再添加任何边缘，正如donkopotamus所指出的那样。最大权匹配意味着没有匹配具有更多的边缘。这就是为什么函数被这样命名的原因。

话虽如此，在图论中并不存在最大基数匹配。但不幸的是，文档使用了“最大基数匹配”这个措辞。这很容易让人们感到困惑；或者更糟糕的是误解算法的目的。

- Cyriac Antony