Aparallament màxim en un graf bipartit P17458

Un graf bipartit és un graf $G = (U \cup V,\, E)$ on els vèrtexs es divideixen en dos conjunts disjunts $U$ i $V$ tals que totes les arestes connecten un vèrtex de $U$ amb un de $V$.

Un aparellament (matching) $M \subseteq E$ és un subconjunt d’arestes tal que cap parell d’arestes de $M$ comparteixen cap vèrtex. La mida d’un aparellament és el nombre d’arestes que conté.

Un aparellament és un aparellament màxim si no existeix cap altre aparellament de mida més gran.

Per exemple, a la figura següent, el primer graf bipartit té un aparellament màxim de 3 arestes que es mostren en negreta i el segon té un aparellament màxim de 5 arestes.

Implementeu un algorisme per trobar la mida d’un aparellament màxim en un graf bipartit.

Entrada

L’entrada consisteix en un graf bipartit descrit per una seqüència d’arestes, cadascuna d’elles descrita per un parell de vèrtexs (paraules) $u$ $v$ de forma que $u \in U$ i $v \in V$.

Sortida

La sortida és la mida d’un aparellament màxim del graf bipartit donat.

Codi utilitzable

Descarregeu-vos el fitxer code.py. Aquest fitxer conté una classe amb la implementació de l’algorisme de Ford-Fulkerson per trobar el flux màxim en una xarxa amb capacitats i un programa principal que l’utilitza.