Find all maximum matchings in a bipartite graph. And how to relabel edges of a bipartite graph in sage?

bipartite

asked 2018-05-13 13:31:12 +0200

I want to find all the maximum matchings in a bipartite graph using sage, an algorithm is given in "Finding all maximally-matchable edges in a bipartite graph " by Tamir Tassa. Also, I want to relabel the edges of my bipartite graph from 0,1,2,.. to y_1, y_2, x_1,.. ,x_1 (dot),...

edit retag flag offensive close merge delete

Comments

What have you tried ?

tmonteil ( 2018-05-15 00:14:47 +0200 )edit

Please initialize a graph, at least. Potential helpers can thus get started. (It would be a big favour if somebody finds, reads the cited text, implements it (in all possible relevant cases). So please come as much as possible with hints, and with a concrete description.)

Relabeling is simpler, e.g.

sage: G = graphs.PetersenGraph()
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.relabel( dict( [ (j, 'y_%s'%j ) for j in range(10) ] ) )
sage: G
Petersen graph: Graph on 10 vertices
sage: G.vertices()
['y_0', 'y_1', 'y_2', 'y_3', 'y_4', 'y_5', 'y_6', 'y_7', 'y_8', 'y_9']