Ask Your Question

How to compute a perfect matching in a general graph?

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

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-29 01:36:01 +0100

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

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

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

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 +0100

Seen: 360 times

Last updated: Jul 29 '19