Aparellament màxim en un graf bipartit

Un graf bipartit és un graf G = (U ∪ 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 ⊆ 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.

[image] [image]

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 ∈ U i v ∈ 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.

Informació del problema

Autoria: Jordi Petit

Generació: 2026-06-04T13:05:16.826Z

© Jutge.org, 2006–2026.
https://jutge.org
