График разложения идеального согласования в двудольном графе

Question

Я ищу алгоритм, который показывает идеальное соответствие разложения Graph в двудольном графе. Я знаю теорию этой проблемы, но я не могу разработать этот алгоритм в Python.

Def: разложение с идеальным совпадением - это разложение, при котором каждый подграф Hi в разложении является идеальным совпадением (идеальное совпадение сопоставление M в графе G - это сопоставление, при котором каждая вершина G инцидентна одному из ребер M)

, поскольку я новичок в python, не могли бы вы рассказать мне о приведенном ниже коде ( как я могу проверить, что это идеальный совпадающий график разложения или нет?) вершины: 20 и степень должны быть между 4 и 8

import networkx as nx
from networkx import bipartite

def plotGraph(graph):
import matplotlib.pyplot as plt
fig=plt.figure()
ax=fig.add_subplot(111)

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)
plt.show(block=False)
return

def enumMaximumMatching(g):
all_matches=[]
return all_matches

if __name__=='__main__':
g=nx.Graph()
edges=[
    [(1,0), (0,0)],
    [(1,0), (0,8)],
    [(1,0), (0,7)],
    [(1,0), (0,5)],
    [(1,0), (0,6)],
    [(1,1), (0,7)],
    [(1,1), (0,0)],
    [(1,1), (0,9)],
    [(1,1), (0,4)],
    [(1,1), (0,8)],
    [(1,1), (0,6)],
    [(1,2), (0,2)],
    [(1,2), (0,3)],
    [(1,2), (0,8)],
    [(1,2), (0,0)],
    [(1,3), (0,9)],
    [(1,3), (0,7)],
    [(1,3), (0,6)],
    [(1,3), (0,5)],
    [(1,3), (0,4)],
    [(1,3), (0,3)],
    [(1,4), (0,3)],
    [(1,4), (0,0)],
    [(1,4), (0,2)],
    [(1,4), (0,8)],
    [(1,5), (0,2)],
    [(1,5), (0,6)],
    [(1,5), (0,7)],
    [(1,5), (0,8)],
    [(1,5), (0,0)],
    [(1,6), (0,1)],
    [(1,6), (0,7)],
    [(1,6), (0,5)],
    [(1,6), (0,6)],
    [(1,7), (0,4)],
    [(1,7), (0,3)],
    [(1,7), (0,2)],
    [(1,7), (0,1)],
    [(1,8), (0,8)],
    [(1,8), (0,9)],
    [(1,8), (0,7)],
    [(1,8), (0,6)],
    [(1,9), (0,4)],
    [(1,9), (0,3)],
    [(1,9), (0,2)],
    [(1,9), (0,1)],
    [(1,9), (0,5)],
    [(1,6), (0,2)],
    [(1,6), (0,9)],

]

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

g.add_edges_from(edges)
plotGraph(g)

all_matches=enumMaximumMatching(g)

for mm in all_matches:
    g_match=nx.Graph()
    for ii in mm:
        g_match.add_edge(ii[0],ii[1])
    plotGraph(g_match)

Спасибо