sage: g=Graph(6)
sage: g.add_edge(0,1)
sage: g.add_edge(1,2)
sage: g.add_edge(0,5)
sage: g.add_edge(1,5)
sage: g.add_edge(5,4)
sage: g.add_edge(2,4)
sage: g.add_edge(2,3)
g.show()
sage: p=MixedIntegerLinearProgram(maximization=True)
sage: b=p.new_variable()
B=lambda u,v : b[(u,v) if u<v else (v,u)]
for u in g:
p.add_constraint(sum([B(u,v) for v in g.neighbors(u)]), max = 1)
for (u,v) in g.edges(labels=None):
p.add_constraint(B(u,v) <= 1)
p.add_constraint(B(u,v) >= 0)
sage: p.set_objective(sum([B(u,v) for (u,v) in g.edges(labels=None)]))
sage: p.write_lp("max_matching_sage.lp")
sage: print("the obj function = ")
sage: p.solve()
sage: b=p.get_values(b)
sage: m = [(u,v) for (u,v) in g.edges(labels=None) if B(u,v)>0]
sage: print("@@@@@ The Maximum Matching @@@@@")
sage: print(m)
sage: g.show(edge_colors={"blue":m})
the obj function =
3.0000000000035003
@@@@@ The Maximum Matching @@@@@
[(0, 1), (1, 5), (2, 3), (2, 4), (4, 5)]