networkx maximal_matching()이 최대 일치를 반환하지 않습니다.

Question

networkx bipartite 그래프의 일부 일치를 수행하기 위해 파이썬 모듈을 사용하는 방법을 배우고 있습니다. maximal_matching 이름으로되지만, 그 문서는 "이것은 그 상태를 수행하는 것이

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

주의 : 그래프의 최대 카디널리티 정합을 제공 모듈의 두 가지 기능이있다 그래프에서 일치하는 최대 카디널리티를 찾으십시오. "

그래프가 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의 구현에서이 버그가 있습니까? 아니면 여기서 잘못된 것이 있습니까?

추신 : 내 networkx이 this bug report에 대한 대답에 따라 버전 1.11

Answer 1

알고리즘 최대 카디널리티이 의도 한 방식대로 일치하지 않습니다. 추가의 엣지를 추가 할 수없는 순수한 그리 디 알고리즘을 구현합니다.

그것의 대응은, 당신이하고자하는 세계 최대 카디널리티 경기, 그래프 이론 용어로 networkx.max_weight_matching

Answer 2

이며, 반환 일치 오히려 최대 일치보다 최대입니다. 어떤 용어를 사용했는지 (나는 이것이 얼마나 일반적인 지 모른다)는 그것이 전체적인 최적 이라기보다 지역적인 최적을주는 것을 의미한다.

따라서 maximal_matching에 의해 반환 된 일치 항목의 경우 해당 일치 항목에 가장자리를 추가하여 더 큰 항목으로 만들 수는 없습니다 (여전히 일치하는 항목 임). 그러나 더 많은 모서리가있는 일치 항목이 존재하지 않는다고 보장 할 수는 없습니다.

Answer 3

이며, 최대 일치 최대 일치 (심지어 이분 그래프) 다릅니다. 최대 일치는 donkopotamus가 지적한대로 더 이상 가장자리를 추가 할 수 없다는 것을 의미합니다. 최대 일치는 일치하는 항목이 더 많지 않음을 의미합니다. 이것이 기능이 이렇게 명명 된 이유입니다.

즉, 그래프 이론에서 최대 카디널리티 일치와 같은 것은 없습니다. 그러나 유감스럽게도 문서에서는 "최대 카디널리티 일치"라는 표현을 사용합니다. 이것은 쉽게 사람들이 혼란에 빠지게합니다. 또는 알고리즘의 목적을 잘못 이해할 수 있습니다.