networkx maximal_matching（）が最大一致を返しません

Question

networkx Pythonモジュールを使用して、2部グラフのマッチングを行うことを学んでいます。 maximal_matchingの名前を持つが、そのドキュメントが「それている状態をしていること

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

注：グラフの最大基数マッチングを与えるモジュール内の2つの機能がありますグラフ内で最大のカーディナリティマッチングを見つける。

私のグラフは2部構成なので、これらの2つは同じ結果を出すと仮定します。しかし、私のコードは、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つのエッジがあり、3には7があります。これはnetworkxの実装のバグですか、ここで何か間違っていますか？

PS：私のnetworkxはバージョン1.11

Answer 1

アルゴリズム最大カーディナリティは、意図したとおりに一致しません。追加のエッジを追加することができないという意味で最大限の結果をもたらすシンプルなグリーディーアルゴリズムを実装しています。

その相手方は、あなたが意図するグローバル最大カーディナリティの試合のために、グラフ理論の用語でnetworkx.max_weight_matching

Answer 2

this bug reportへの回答によると、返されたマッチングではなく、最大のマッチングよりも、最大です。彼らの専門用語（私はこれがどれほど共通しているか分かりません）は、それが大域最適ではなく局所最適を与えることを意味します。

maximal_matchingから返されたマッチングでは、そのマッチングにエッジを追加することで（マッチしている間に）エッジを追加することで大きなマージンを作ることはできません。ただし、より多くのエッジを持つ一致が存在しないことは保証されません。

Answer 3

で、最大マッチングと最大マッチングが（でも二部グラフで）異なっています。マキシマムマッチングとは、ドンコポタマスが指摘しているように、それ以上エッジを追加できないということです。マッチングが最大であるということは、マッチングがそれ以上のエッジを持たないことを意味このため、関数の名前が付けられています。

つまり、グラフ理論で最大のカーディナリティマッチングというものはありません。しかし残念なことに、ドキュメンテーションは "最大カーディナリティマッチング"という表現を使用しています。これは簡単に人々が混乱することにつながります。アルゴリズムの目的を誤解することがあります。