El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència

HOME

Última lliçó del mòdul, i tanquem amb el problema més humà de tots: aparellar. Cada matí Rutalia ha d'assignar repartidors a torns i comandes, i no tothom pot amb tot: qui va amb bicicleta no cobreix el Polígon, qui no té carnet de moto no fa el torn exprés del Centre. A 03-05 vam deixar la pista: l'assignació és un flux amb capacitats 1. Aquí la desenvolupem amb la seva teoria pròpia —grafs bipartits, camins alternants i augmentants—, implementem l'algorisme clàssic d'aparellament màxim, presentem l'algorisme hongarès per a la versió amb costos, i tanquem el cercle amb l'assignació òptima que a 02-01 resolíem amb programació lineal. En acabar, passarem revista a l'arsenal complet de grafs del mòdul.

Contingut

Grafs bipartits i el test de bipartició amb BFS
Aparellaments: definicions i el fracàs del voraç
Aparellament màxim via flux: la reducció explícita
Camins alternants i augmentants: l'algorisme directe
Aparellament amb pesos: l'algorisme hongarès i scipy
L'arsenal de grafs del mòdul 3, en una taula

Grafs bipartits i el test de bipartició amb BFS

Un graf és bipartit si els seus vèrtexs poden dividir-se en dos grups L i R de manera que tota aresta creui d'un grup a l'altre (cap aresta interna). El graf repartidors–torns és bipartit per construcció: les arestes només uneixen persones amb torns compatibles, mai persona amb persona.

Caracterització clau: un graf és bipartit si i només si no conté cicles de longitud senar. I el test és un BFS de 03-02 amb un extra mínim — pintar per nivells alterns i vigilar contradiccions:

from collections import deque

def es_bipartit(graf):
    """2-coloracio per BFS. Retorna (True, color) o (False, None)."""
    color = {}
    for inici in graf:                      # cobreix grafs no connexos
        if inici in color:
            continue
        color[inici] = 0
        cua = deque([inici])
        while cua:
            u = cua.popleft()
            for v in graf[u]:
                if v not in color:
                    color[v] = 1 - color[u]     # nivell seguent, color oposat
                    cua.append(v)
                elif color[v] == color[u]:      # aresta entre el mateix color
                    return False, None          # cicle senar: no bipartit
    return True, color

Dues proves il·lustratives:

La xarxa canònica de Rutalia (03-01) no és bipartita: conté el triangle ALM–MER–CEN (cicle de longitud 3, senar). El test ho detecta tan bon punt el BFS intenta pintar el tercer vèrtex del triangle.
El graf de compatibilitats d'aquesta lliçó sí que ho és, amb L = repartidors i R = torns. En general, el test serveix quan la bipartició no ve donada (puc dividir aquestes zones en "parelles/senars" per repartir en dies alterns sense que dues zones veïnes coincideixin? — mateixa pregunta, mateix BFS).

Aparellaments: definicions i el fracàs del voraç

Un aparellament (matching) M és un subconjunt d'arestes sense vèrtexs en comú: ningú no apareix en dues parelles. Vocabulari:

Un vèrtex és lliure si cap aresta de M no el toca.
M és màxim (maximum) si cap aparellament no té més arestes. Compte amb el fals amic maximal: "no ampliable afegint arestes soltes", que pot ser molt pitjor.
M és perfecte si no deixa cap vèrtex lliure.

Instància central de la lliçó — 4 repartidors, 4 torns, compatibilitats per vehicle i zona (dades fictícies):

	Nord	Sud	Centre	Riu
Ana	✓		✓
Bruno	✓			✓
Carla		✓	✓
Dani	✓

graph LR
    Ana --- Nord
    Ana --- Centre
    Bruno --- Nord
    Bruno --- Riu
    Carla --- Sud
    Carla --- Centre
    Dani --- Nord

Prova l'enfocament voraç (assignar en ordre a cadascú el primer torn lliure): Ana→Nord, Bruno→Riu, Carla→Sud… i Dani es queda sense torn, perquè la seva única opció (Nord) està ocupada. Tres parelles i un aparellament maximal però no màxim: n'existeix un de perfecte. El voraç torna a fallar (02-02 ens va vacunar), però aquesta vegada la reparació no exigeix backtracking exponencial: hi ha estructura per explotar.

Aparellament màxim via flux: la reducció explícita

Primera solució: cobrar l'avançament de 03-05. La reducció converteix l'aparellament en un flux:

Font s → cada repartidor amb capacitat 1.
Repartidor → torn compatible, capacitat 1, dirigida cap al torn.
Cada torn → embornal t, capacitat 1.

def aparellament_per_flux(compatibles, torns):
    """compatibles: {repartidor: [torns]}. Reutilitza edmonds_karp de 03-05."""
    xarxa = {"s": {r: 1 for r in compatibles}, "t": {}}
    for r, ts in compatibles.items():
        xarxa[r] = {t_: 1 for t_ in ts}
    for t_ in torns:
        xarxa[t_] = {"t": 1}
    valor, res, _ = edmonds_karp(xarxa, "s", "t")
    # una aresta repartidor->torn amb residual 0 ha quedat saturada: es parella
    parelles = {r: t_ for r, ts in compatibles.items()
                for t_ in ts if res[r][t_] == 0}
    return valor, parelles

COMPAT = {"Ana": ["Nord", "Centre"], "Bruno": ["Nord", "Riu"],
          "Carla": ["Sud", "Centre"], "Dani": ["Nord"]}
print(aparellament_per_flux(COMPAT, ["Nord", "Sud", "Centre", "Riu"]))
# (4, {'Ana': 'Centre', 'Bruno': 'Riu', 'Carla': 'Sud', 'Dani': 'Nord'})

Tres observacions de pes:

Les capacitats 1 codifiquen "cada persona un torn, cada torn una persona"; la integralitat de Ford-Fulkerson (03-05) garanteix parelles enteres, no mitges assignacions.
El flux màxim (4) és la mida de l'aparellament màxim: hi ha assignació perfecta, el voraç simplement no la trobava.
Amb Edmonds-Karp sobre aquesta xarxa el cost queda en O(n·m) per a grafs bipartits amb capacitats unitàries (cada augment suma 1 i hi ha com a molt n augments). Existeix un algorisme especialitzat més ràpid (Hopcroft-Karp, O(m·√n)); mateix principi, augments per lots.

Camins alternants i augmentants: l'algorisme directe

La reducció funciona, però val la pena veure la maquinària sense la disfressa de flux, perquè té nom propi i una teoria elegant. Donat un aparellament M:

Un camí alternant alterna arestes fora de M i dins de M.
Un camí augmentant és un camí alternant que comença i acaba en vèrtexs lliures.

Si existeix un camí augmentant, es pot millorar M: s'inverteixen les seves arestes (les que eren fora entren, les que eren dins surten) i l'aparellament guanya exactament una parella. Al nostre exemple, amb el voraç encallat a 3, el camí augmentant és:

Dani (lliure) — Nord (aresta fora de M) — Ana (parella actual de Nord) — Centre (fora de M, i Centre està lliure).

Invertir: Dani–Nord entra, Ana–Nord surt, Ana–Centre entra. Resultat: 4 parelles. El teorema de Berge tanca la teoria: M és màxim si i només si no existeix cap camí augmentant. És l'anàleg exacte del "no hi ha camí augmentant a la residual" de 03-05 — de fet, un camí augmentant de matching és un camí augmentant de flux mirat sense la font ni l'embornal.

L'algorisme clàssic (algorisme de Kuhn) busca un camí augmentant des de cada repartidor lliure amb un DFS que "desallotja" recursivament:

def aparellament_augmentant(compatibles):
    """Aparellament maxim bipartit per camins augmentants (Kuhn)."""
    parella_torn = {}                      # torn -> repartidor assignat

    def intenta(r, vetats):
        """DFS: pot r aconseguir torn, reubicant qui calgui?"""
        for t in compatibles[r]:
            if t in vetats:
                continue                   # ja explorat en AQUEST intent
            vetats.add(t)
            ocupant = parella_torn.get(t)
            # t esta lliure, o el seu ocupant pot mudar-se a un altre torn
            if ocupant is None or intenta(ocupant, vetats):
                parella_torn[t] = r        # (re)assignacio en cascada
                return True
        return False

    total = sum(intenta(r, set()) for r in compatibles)
    return total, {r: t for t, r in parella_torn.items()}

print(aparellament_augmentant(COMPAT))
# (4, {'Ana': 'Centre', 'Bruno': 'Nord', 'Carla': 'Sud', 'Dani': ...})

Com llegir el DFS, que és el cor de l'algorisme:

intenta(r, ...) pregunta: pot r quedar aparellat? Recorre els seus torns compatibles; si un és lliure, fet. Si està ocupat, pregunta recursivament si l'ocupant pot mudar-se — això és, literalment, recórrer un camí alternant.
vetats evita cicles dins d'un mateix intent (cada torn es considera una vegada per cerca), garantint O(m) per repartidor: O(n·m) total.
La cascada de reassignacions en retornar True és la "inversió del camí augmentant" feta codi: cada nivell de la recursió reescriu una parella.
El resultat concret (qui acaba amb què) pot variar amb l'ordre d'exploració; la mida de l'aparellament, mai — Berge ho garanteix.

Important delimitar el terreny: tot l'anterior és per a grafs bipartits. En grafs generals (aparellar repartidors entre si per a rutes en tàndem, per exemple) els cicles senars compliquen els camins alternants i cal l'algorisme de Blossom d'Edmonds — existeix, és polinòmic, i queda fora de l'abast del curs.

Aparellament amb pesos: l'algorisme hongarès i `scipy`

Fins aquí, compatibilitat binària: pot o no pot. La realitat de Rutalia és més fina: tothom pot amb gairebé tot, però a diferent cost (minuts des de la base de cada repartidor fins a la zona del torn). El problema passa a ser el problema d'assignació: aparellament perfecte de cost mínim.

Cost (min)	Nord	Sud	Centre	Riu
Ana	4	9	3	8
Bruno	6	7	5	2
Carla	8	2	6	9
Dani	3	10	7	6

L'algorisme hongarès el resol en O(n³). A nivell conceptual (suficient per a aquest curs):

Restar a cada fila el seu mínim i a cada columna el seu: els costos es tornen ≥ 0 amb almenys un 0 per fila i columna. Restar una constant a una fila no canvia quina assignació és òptima (totes les assignacions usen exactament una cel·la d'aquella fila) — només en canvia el valor.
Buscar un aparellament perfecte usant només cel·les 0: és exactament un aparellament màxim bipartit sense pesos, l'algorisme de la secció anterior!
Si no existeix, un ajust de potencials crea nous zeros "ben orientats" i es repeteix. La teoria que ho justifica és la dualitat de programació lineal — el mateix fonament del símplex que vam fregar a 02-01: l'assignació és un PL l'òptim del qual cau sempre en enters.

A la pràctica professional no s'implementa a mà; scipy el porta a punt (és la mateixa assignació òptima que a 02-01 plantejàvem com a PL, ara amb algorisme especialitzat):

import numpy as np
from scipy.optimize import linear_sum_assignment

costos = np.array([
    [4, 9, 3, 8],     # Ana
    [6, 7, 5, 2],     # Bruno
    [8, 2, 6, 9],     # Carla
    [3, 10, 7, 6],    # Dani
])
files, cols = linear_sum_assignment(costos)
print(list(zip(files, cols)))       # [(0, 2), (1, 3), (2, 1), (3, 0)]
print(costos[files, cols].sum())    # 10

Òptim: Ana→Centre (3), Bruno→Riu (2), Carla→Sud (2), Dani→Nord (3) = 10 minuts de desplaçament total. En aquesta instància cada repartidor aconsegueix el seu torn individualment més barat — sort que no sempre es dona: amb costos [[1, 2], [1, 5]] tots dos volen la primera columna, i l'òptim global (2 + 1 = 3) obliga el primer a cedir. Aquesta tensió entre òptim individual i global és justament el que l'hongarès arbitra, i el que el voraç "cadascú al seu mínim" no sap resoldre.

Per maximitzar compatibilitat en lloc de minimitzar cost, n'hi ha prou amb linear_sum_assignment(matriu, maximize=True) (o negar la matriu): mateix algorisme.

L'arsenal de grafs del mòdul 3, en una taula

Mòdul tancat. Aquest és l'arsenal complet, amb la pregunta de negoci que respon cada peça:

Lliçó	Pregunta de Rutalia	Eina	Cost
03-01	Com modelo la ciutat?	(V, E); matriu vs llista d'adjacència	—
03-02	Què és abastable i a quants trams? En quin ordre faig les tasques?	BFS, DFS, components, Kahn	O(n + m)
03-03	Quina és la ruta més ràpida? I entre totes les zones?	Dijkstra (heap), Bellman-Ford, Floyd-Warshall	O((n+m) log n) / O(nm) / O(n³)
03-04	Quina infraestructura mínima ho connecta tot?	Kruskal (union-find), Prim (heap)	O(m log n)
03-05	Quants paquets/hora hi caben i on és el coll d'ampolla?	Edmonds-Karp, max-flow min-cut	O(n·m²)
03-06	Qui fa què, i al mínim cost?	Camins augmentants, hongarès / `scipy`	O(n·m) / O(n³)

I els deutes del curs, saldats: el heap de 01-04 va impulsar Dijkstra i Prim; l'union-find de 01-04 va sostenir Kruskal; la PD de 01-03 va reaparèixer a Floyd-Warshall; el BFS de 03-02 batega dins d'Edmonds-Karp i del test de bipartició; i la matriu de temps de 03-03 és la que alimentava el TSP del mòdul 2.

Errors Comuns i Consells

Confondre maximal amb màxim: el voraç d'Ana/Bruno/Carla produeix un aparellament maximal (no ampliable amb una aresta solta) que deixa Dani a casa. Màxim exigeix camins augmentants; no et refiïs del fet que "ja no puc afegir res".
Aplicar l'algorisme de Kuhn a un graf no bipartit: els cicles senars trenquen l'argument dels camins alternants i el resultat pot ser subòptim sense avís. Executa abans es_bipartit; si falla, el problema és d'aparellament general (Blossom) o de modelatge.
Oblidar el conjunt vetats per intent (o compartir-lo entre intents): sense ell, el DFS pot ciclar; compartit entre repartidors, prohibeix reassignacions legítimes i encongeix el resultat.
Resoldre assignació amb pesos provant permutacions: n! una altra vegada (02-02). Per a n = 15 ja és inviable; l'hongarès ho fa en O(n³) exacte. Reserva la força bruta per verificar en instàncies mínimes.
Matriu de costos no quadrada a linear_sum_assignment: scipy l'admet (assigna només min(files, columnes) parelles), però interpreta que sobren recursos; si necessites "torn sense cobrir = penalització", afegeix columnes fictícies amb aquell cost explícit. Modela, no deixis que l'eina decideixi per tu.
Consell: davant de qualsevol problema de "qui amb qui" (persones-tasques, furgonetes-rutes, comandes-franges), dibuixa el graf bipartit abans de programar. La meitat de les vegades la solució és una reducció directa al que ja tens de 03-05 o d'aquesta lliçó.

Exercicis

Repartiment en dies alterns. Rutalia vol dividir les 9 zones del graf canònic en dos grups (repartiment dilluns/dimecres/divendres davant de dimarts/dijous/dissabte) de manera que cap carrer no uneixi dues zones del mateix grup. Usa es_bipartit per demostrar que és impossible, i identifica a mà un cicle senar que ho certifiqui. N'hi hauria prou d'eliminar una aresta perquè fos possible?
La baixa d'última hora. A la instància central, Carla es dona de baixa i arriba l'Elia, que només pot cobrir Centre: compatibilitats Ana:{Nord, Centre}, Bruno:{Nord, Riu}, Dani:{Nord}, Elia:{Centre}. Existeix assignació perfecta? Executa aparellament_augmentant, i explica el resultat trobant a mà el conjunt de repartidors els torns possibles dels quals "no donen per a més" (pista: teorema de Hall — un aparellament perfecte exigeix que tot grup de k repartidors tingui almenys k torns possibles en conjunt).
Assignació amb incompatibilitats i costos. Combina les dues meitats de la lliçó: sobre la matriu de costos de la secció 5, imposa que Dani no pot cobrir Sud ni Centre (vehicle inadequat). Representa la prohibició amb un cost molt gran (p. ex. 999) i resol amb linear_sum_assignment. Canvia l'assignació òptima respecte de la versió sense restriccions?

Solucions

Exercici 1:

print(es_bipartit(XARXA)[0])   # False

Certificat a mà: el triangle ALM–MER–CEN és un cicle de longitud 3. Amb dos grups, dos d'aquests tres vèrtexs caurien junts i el carrer entre ells violaria la regla. Eliminar una aresta d'aquell triangle no basta en general: hi ha més cicles senars (per exemple ALM–RIO–CEN–ALM? — ALM–RIO, RIO–CEN, CEN–ALM: un altre triangle). Caldria trencar tots els cicles senars, i aquí comparteixen arestes: treure CEN–ALM elimina aquests dos triangles, però queda el cicle de 5 ALM–MER–CEN–HOS–?… la comprovació honesta és rellançar es_bipartit després de cada supressió. Moralitat: la bipartició és una propietat global, no local.

Exercici 2:

COMPAT2 = {"Ana": ["Nord", "Centre"], "Bruno": ["Nord", "Riu"],
           "Dani": ["Nord"], "Elia": ["Centre"]}
print(aparellament_augmentant(COMPAT2))   # (3, ...)

No hi ha assignació perfecta: màxim 3. El certificat de Hall: el grup {Ana, Dani, Elia} només abasta en conjunt els torns {Nord, Centre} — 3 persones, 2 torns possibles: algú es queda fora, triï com triï l'algorisme. Observa la dualitat, ja familiar: quan l'aparellament no pot créixer, existeix un "coll d'ampolla" estructural que ho certifica (aquí el conjunt deficient de Hall; a 03-05 era el tall mínim). Els bons algorismes no només fallen: expliquen per què.

Exercici 3:

costos2 = costos.copy()
costos2[3, 1] = 999   # Dani-Sud prohibit
costos2[3, 2] = 999   # Dani-Centre prohibit
files, cols = linear_sum_assignment(costos2)
print(costos2[files, cols].sum())   # 10

L'assignació no canvia: l'òptim original (Ana→Centre, Bruno→Riu, Carla→Sud, Dani→Nord) ja evitava les cel·les ara prohibides, així que segueix costant 10. La tècnica del "cost 999" és la manera estàndard de barrejar restriccions dures amb optimització tova; verifica sempre que cap cel·la prohibida no aparegui a la solució final (si hi apareix, no existia assignació factible i el 999 t'ho està cridant).

Conclusió

L'aparellament tanca el mòdul unint gairebé totes les seves peces: el test de bipartició és un BFS de 03-02 amb dos colors; l'aparellament màxim és un flux de 03-05 amb capacitats 1, o directament l'algorisme de camins augmentants, la garantia del qual —el teorema de Berge— és germana del max-flow min-cut; i la versió amb costos, resolta per l'algorisme hongarès o scipy.optimize.linear_sum_assignment, retroba l'assignació òptima que a 02-01 formulàvem com a programació lineal. Rutalia disposa ja d'un arsenal complet sobre la seva xarxa urbana: modelar-la (03-01), recórrer-la (03-02), trobar rutes mínimes (03-03), construir infraestructura mínima (03-04), mesurar el seu cabal i els seus colls d'ampolla (03-05) i assignar la seva gent de manera òptima (03-06). Hem recorregut estructures; el pas següent és un altre múscul: cercar i ordenar dins de les dades. Els catàlegs de productes, els registres massius de lliuraments i els històrics de rutes de Rutalia no són grafs sinó volums — milions de files on trobar i ordenar ràpid marca la diferència. Al mòdul 4 comencem per l'eina més esmolada i més traïdora de totes: la cerca binària i les seves variants (04-01).

Algorismes d'Aparellament en Grafs

Contingut

Grafs bipartits i el test de bipartició amb BFS

Aparellaments: definicions i el fracàs del voraç

Aparellament màxim via flux: la reducció explícita

Camins alternants i augmentants: l'algorisme directe

Aparellament amb pesos: l'algorisme hongarès i `scipy`

L'arsenal de grafs del mòdul 3, en una taula

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Algorismes Avançats

Mòdul 1: Introducció als Algorismes Avançats

Mòdul 2: Algorismes d'Optimització

Mòdul 3: Algorismes en Grafs

Mòdul 4: Algorismes de Cerca i Ordenació

Mòdul 5: Algorismes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final

Algorismes d'Aparellament en Grafs

Contingut

Grafs bipartits i el test de bipartició amb BFS

Aparellaments: definicions i el fracàs del voraç

Aparellament màxim via flux: la reducció explícita

Camins alternants i augmentants: l'algorisme directe

Aparellament amb pesos: l'algorisme hongarès i scipy

L'arsenal de grafs del mòdul 3, en una taula

Errors Comuns i Consells

Exercicis

Solucions

Conclusió

Algorismes Avançats

Mòdul 1: Introducció als Algorismes Avançats

Mòdul 2: Algorismes d'Optimització

Mòdul 3: Algorismes en Grafs

Mòdul 4: Algorismes de Cerca i Ordenació

Mòdul 5: Algorismes d'Aprenentatge Automàtic

Mòdul 6: Casos d'Estudi i Aplicacions

Mòdul 7: Projecte Final

Aparellament amb pesos: l'algorisme hongarès i `scipy`