Ask Your Question
0

How to compute a perfect matching in a general graph?

asked 2019-07-28 01:09:48 -0500

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
0

answered 2019-07-28 18:36:01 -0500

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
0

answered 2019-07-28 14:17:22 -0500

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

Stats

Asked: 2019-07-28 01:09:48 -0500

Seen: 42 times

Last updated: Jul 28 '19