Ask Your Question
1

Check SDR in a bipartite graph by Hall's theorem.

asked 2015-12-07 10:39:04 -0500

vicarious gravatar image

How can I check existence of a complete SDR in a bipartite graph ?

This will be done by checking if there is a perfect matching in the graph(Hall's marriage theorem), but How can I implement this in SAGE?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2015-12-07 10:49:08 -0500

tmonteil gravatar image

You can ask for a maximal matching and see if its size correspond to half the size of the bipartite graph:

You can get a maximal matching as follows:

sage: n = 10
sage: G = graphs.RandomBipartite(n,n,0.5)
sage: G.matching()
[((0, 1), (1, 0), None),
 ((0, 6), (1, 7), None),
 ((0, 4), (1, 4), None),
 ((0, 7), (1, 8), None),
 ((0, 9), (1, 9), None),
 ((0, 0), (1, 2), None),
 ((0, 5), (1, 6), None),
 ((0, 3), (1, 1), None),
 ((0, 8), (1, 5), None),
 ((0, 2), (1, 3), None)]

You can check that a maximal matching is complete as follows:

sage: len(G.matching()) == n
True

or as follows:

sage: G.matching(value_only=True) == n
True
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

Stats

Asked: 2015-12-07 10:39:04 -0500

Seen: 254 times

Last updated: Dec 07 '15