Sparivanja prikazana na slici

import networkx as nx
import itertools as it
import numpy as np
import matplotlib.pyplot as plt

G = nx.read_adjlist("graf.adjlist")

def all_maximal_matching(G, number):
    max_matching = []
    for x in it.combinations(G.edges(), number):
        if nx.is_matching(G, set(x)):
            if nx.is_maximal_matching(G,set(x)):
                max_matching.append(set(x))
    print("Ukupno: ", len(max_matching))
    return max_matching

Sva maksimalna sparivanja s tri brida u grafu G

maxSpar3 = all_maximal_matching(G, 3)

Ukupno:  19

fig, ax = plt.subplots(4, 5, figsize=(25, 20))
[axi.axis('off') for axi in ax.ravel()]
for indeks, matching in enumerate(maxSpar3):
    nx.set_edge_attributes(G, 'k', 'color')
    nx.set_edge_attributes(G, 1, 'weight')
    nx.set_edge_attributes(G,dict(zip(matching,[{"color": 'b', "weight": 4}]*3)))
    xy = np.unravel_index(indeks, ax.shape)
    plt.sca(ax[xy])
    nx.draw_circular(G, with_labels=True, node_color="yellow", edgecolors="black", 
                        edge_color=nx.get_edge_attributes(G,'color').values(),  
                        width=list(nx.get_edge_attributes(G,'weight').values()), ax=ax[xy])

Sva najveća sparivanja u grafu G

maxSpar4 = all_maximal_matching(G, 4)

Ukupno:  17

fig, ax = plt.subplots(4, 5, figsize=(25, 20))
[axi.axis('off') for axi in ax.ravel()]
for indeks, matching in enumerate(maxSpar4):
    nx.set_edge_attributes(G, 'k', 'color')
    nx.set_edge_attributes(G, 1, 'weight')
    nx.set_edge_attributes(G,dict(zip(matching,[{"color": 'b', "weight": 4}]*4)))
    xy = np.unravel_index(indeks, ax.shape)
    nx.draw_circular(G, with_labels=True, node_color="yellow", edgecolors="black", 
                        edge_color=nx.get_edge_attributes(G,'color').values(),  
                        width=list(nx.get_edge_attributes(G,'weight').values()), ax=ax[xy])