Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 20
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)]