Ask Your Question

How to compute a perfect matching in a general graph?

asked 2019-07-28 08:09:48 +0200

Ganapati Natarajan gravatar image

Are there functions to compute a maximal or perfect matching, or all the maximal/perfect matchings in a general (bipartite or non-bipartite) graph

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2019-07-28 21:17:22 +0200

tmonteil gravatar image

If you just want a perfect matching, you can use:

sage: p = G.matching()

If you want to iterate over all parfect matching, you can use (but it might be very slow as it is a brute force approach):

sage: for p in G.perfect_matchings():
....:     blah
edit flag offensive delete link more

answered 2019-07-29 01:36:01 +0200

dazedANDconfused gravatar image

You should download the PDF documentation which is available here. On page 222 there are 3 listed:

  1. matching() Return a maximum weighted matching of the graph represented by the list of its edges.
  2. has_perfect_matching() Return whether this graph has a perfect matching
  3. perfect_matchings() Return an iterator over all perfect matchings of the graph.

Clicking on each method will bring you to more instructions and examples.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-07-28 08:09:48 +0200

Seen: 412 times

Last updated: Jul 29 '19