A la lliçó anterior vam aprendre a moure'ns per la xarxa de Rutalia al mínim cost. Aquesta lliçó planteja un problema diferent que sona semblant i s'hi confon constantment: no volem anar d'un lloc a un altre, volem connectar-ho tot gastant el mínim. Rutalia desplegarà una xarxa d'armariets intel·ligents a les 9 zones de la ciutat, units per fibra òptica estesa al llarg dels carrers: quins trams cal cablejar perquè tots els armariets quedin comunicats amb el menor cost total d'obra? La resposta és l'arbre d'expansió mínim (MST), i porta dos regals: la segona llavor de 01-04 —l'union-find que sosté Kruskal— i una lliçó profunda sobre algorismes voraços: aquí, a diferència dels contraexemples de 02-02, l'avarícia és demostrablement òptima.

1. Arbres d'expansió: definició i per què el mínim importa
2. La propietat del tall: per què el voraç aquí SÍ que és òptim
3. Kruskal: ordenar arestes i collir la llavor de l'union-find
4. Prim: fer créixer l'arbre amb un heap
5. Kruskal vs Prim: taula i criteri d'elecció
6. MST vs camins mínims: l'arbre de Dijkstra NO és el MST

Un arbre d'expansió (spanning tree) d'un graf connex G = (V, E) és un subconjunt d'arestes que connecta tots els vèrtexs i no conté cicles. Com tot arbre, té exactament n − 1 arestes: ni una més (hi hauria cicle) ni una menys (quedaria alguna cosa solta). Un graf té en general moltíssims arbres d'expansió; l'arbre d'expansió mínim (MST) és el de menor suma de pesos.

Per què "arbre"? Pensa en la fibra dels armariets: si el cablejat formés un cicle, podries treure qualsevol aresta del cicle i tot seguiria connectat — hauries pagat una rasa inútil. La solució òptima d'un problema de connexió pura mai no conté cicles; per tant, és un arbre.

Per a la xarxa d'armariets reutilitzem el graf canònic de 03-01 reinterpretant els pesos: on abans llegíem "minuts de furgoneta", ara llegim "cost d'obra en milers d'euros" (proporcional a la longitud del tram, així que els mateixos números serveixen). La pregunta: quins 8 trams dels 15 es cablegen?

Aplicacions del mateix patró, més enllà de la fibra: xarxes elèctriques i d'aigua, disseny de circuits, agrupament de dades (el clustering jeràrquic de 05-05 té el MST amagat a dins), i aproximacions al TSP (el famós 2-aproximat es construeix passejant per un MST).

A 02-02 vam veure algorismes voraços estavellar-se: el "veí més proper" del TSP donava 43,1 km davant de l'òptim de 35,22, i la motxilla per valor/pes fallava amb contraexemples de tres objectes. La pregunta honesta és: per què aquí ha de funcionar triar "l'aresta més barata"? La resposta té nom propi:

Propietat del tall. Divideix els vèrtexs en dos grups no buits (S, V∖S) — un tall. Entre totes les arestes que creuen el tall, sigui e la de pes mínim (suposa pesos diferents per simplificar). Aleshores e pertany a tot MST.

Demostració per intercanvi (la tècnica clàssica per justificar voraços): suposa un arbre d'expansió T que no conté e = {u, v}. Com que T connecta u amb v, conté un camí entre tots dos, i aquell camí creua el tall per almenys una aresta f (≠ e, i per definició d'e: pes(f) > pes(e)). Treu f i afegeix e: el resultat T′ segueix connectant-ho tot (e reempalma les dues meitats que treure f havia separat), segueix tenint n−1 arestes, i pesa menys que T. Per tant T no era mínim. ∎

La moralitat general, que val el seu pes en or: el voraç no és fiable ni sospitós per defecte; és correcte exactament quan el problema té una estructura d'intercanvi que ho garanteix. El MST la té (els matemàtics diuen que les arestes sense cicles formen una matroide); el TSP i la motxilla 0/1, no. Dijkstra (03-03) era l'altre voraç amb certificat: el seu invariant era també un argument d'intercanvi disfressat.

Tots dos algorismes d'aquesta lliçó són aplicacions directes de la propietat del tall; només canvia quins talls miren.

Estratègia de Kruskal: recórrer les arestes de més barata a més cara, acceptant-ne cadascuna llevat que formi cicle amb les ja acceptades. La propietat del tall el respalda: quan una aresta {u, v} és acceptada, és la més barata que creua el tall "component d'u davant de la resta" (totes les més barates ja s'han processat i no separaven aquelles meitats).

I com es detecta "forma cicle" eficientment? Una aresta forma cicle si els seus dos extrems ja són a la mateixa component. És a dir: necessitem pertinença a components amb arestes que van arribant una a una — exactament el cas que a 03-02 vam dir que BFS resol malament i union-find resol de meravella. La llavor de 01-04, collida:

Traça completa sobre la xarxa d'armariets — el "vídeo" de l'algorisme:

Cost total de l'obra: 37.000 €, davant dels 87.000 que costaria cablejar els 15 trams. Fixa't en què rebutja Kruskal: justament les arestes "redundants" que tancarien anells — inclosa l'avinguda ALM–CEN de 12, que ni tan sols arriba a examinar-se.

Complexitat: ordenar domina, O(m log m) = O(m log n); les 2m operacions d'union-find costen O(m · α(n)) — aquella α, la inversa d'Ackermann que vam veure a 01-04, és ≤ 4 per a qualsevol graf del món físic. A la pràctica: "ordenar + gairebé gratis".

Prim aplica la mateixa propietat del tall amb una altra tàctica: mantenir un únic arbre que creix des d'un node inicial, afegint a cada pas l'aresta més barata que surt de l'arbre cap enfora (el tall és sempre "arbre actual davant de la resta"). I qui lliura "l'aresta més barata de la frontera"? Una altra vegada el heap de 01-04 — el mateix motor que Dijkstra, amb una diferència crucial en la prioritat:

Compara mentalment amb el Dijkstra de 03-03: mateix esquelet (heap, tancats, esborrat mandrós), però la tupla del heap porta pes_de_l_aresta en lloc de distancia_acumulada. Aquest únic canvi transforma "ser a prop de l'origen" en "ser a prop de l'arbre". De nou la gran família: cua→BFS, pila→DFS, heap per distància→Dijkstra, heap per aresta→Prim.

Complexitat amb heap binari: cada aresta entra com a molt una vegada al heap ⇒ O(m log n), com Kruskal. Amb matriu d'adjacència i sense heap existeix una variant O(n²), que en grafs densos (m ≈ n²) és de fet millor.

Per a la xarxa d'armariets (dispersa: 15 arestes, 9 nodes) tots dos són instantanis i idèntics en resultat; a escala de ciutat, Kruskal sol ser el més còmode en grafs viaris dispersos, i Prim O(n²) guanya en grafs densos tipus "matriu de distàncies tot-amb-tot". Si els pesos són tots diferents, el MST és únic i tots dos retornen exactament el mateix arbre; amb empats poden diferir en arestes, mai en el cost total.

Dijkstra també produeix un arbre (el de pares, amb n−1 arestes). És temptador creure que aquell arbre és el MST: no ho és, i confondre'ls és un error de disseny car. Optimitzen coses diferents:

• Arbre de Dijkstra des de s: minimitza la distància de s a cada node. Serveix el repartidor que surt del magatzem.
• MST: minimitza la suma total de les arestes triades. Serveix qui paga les rases de la fibra.

Contraexemple mínim, tres zones:

• MST: {A–B, B–C}, cost total 2 (descarta l'aresta d'1,5).
• Arbre de Dijkstra des d'A: fins a C convé la directa (1,5 < 1+1), així que {A–B, A–C}, cost total 2,5.

Cap dels dos no "s'equivoca": al MST, anar d'A a C costa 2 (fent la volta per B) tot i que la xarxa sencera surti més barata; a l'arbre de Dijkstra, C és a 1,5 però la infraestructura total és més cara. I a la xarxa de Rutalia la diferència és escandalosa: l'arbre de Dijkstra des d'ALM pesa 46 (usa ALM–EST 7, MER–UNI 6, RIO–PAR 8, EST–IND 9), mentre que el MST pesa 37 (prefereix EST–UNI 3, UNI–HOS 5, IND–HOS 6, PAR–HOS 7). Un 24% més car per optimitzar la mètrica equivocada.

• Usar l'arbre de Dijkstra com a xarxa d'infraestructura (o el MST com a taula de rutes): el contraexemple de tres nodes hauria de bastar; a Rutalia la confusió costa un 24% de sobrecost o rutes absurdes. Primer decideix què es minimitza, després tria algorisme.
• Detectar cicles a Kruskal amb BFS/DFS sobre les arestes acceptades: correcte però O(n) per aresta ⇒ O(n·m) total. L'union-find ho deixa en α(n) per consulta; per a això el vam sembrar a 01-04.
• Oblidar la compressió de camins o la unió per rang: l'union-find degenera en llistes i find es torna O(n). Són quatre línies; escriu-les sempre.
• No aturar-se en arribar a n−1 arestes a Kruskal: el resultat segueix sent correcte (tota la resta es rebutjaria), però es processen arestes cares inútilment. El break és gratis.
• Aplicar MST a un graf no connex: no existeix arbre d'expansió; Kruskal retorna silenciosament un bosc d'expansió mínim. Comprova len(mst) == n - 1 en acabar i decideix què significa el dèficit al teu problema (a Rutalia: zones sense fibra).
• Consell: quan un voraç et tempti, busca l'argument d'intercanvi ("si la solució òptima no usés la meva elecció, la canvio i no empitjora"). Si el trobes, tens algorisme i demostració; si no apareix, sospita — recorda el veí més proper del TSP.

1. La fibra que faltava. L'ajuntament prohibeix obrir rasa al tram UNI–HOS (cost 5). Recalcula el MST amb Kruskal sense aquesta aresta. Quant encareix la prohibició? Quina aresta hi entra en substitució, i per què justament aquella, a la llum de la propietat del tall?
2. Aresta segura a mà. Sense executar cap algorisme, usa la propietat del tall amb S = {IND} per demostrar quina aresta incident a IND és a tot MST de la xarxa d'armariets. Verifica-ho contra la traça de Kruskal.
3. Kruskal com a agrupador. Si atures Kruskal quan queden exactament 3 components, obtens una partició de les zones en 3 grups "naturalment propers" (així funciona el clustering d'enllaç simple, que reapareixerà a 05-05). Modifica kruskal perquè accepti un paràmetre k_components i calcula els 3 grups de la xarxa d'armariets.

Exercici 1:

Hi entra MER–UNI (6) en lloc d'UNI–HOS (5). Explicació per tall: en eliminar UNI–HOS, en el moment en què Kruskal té els fragments {ALM,RIO,MER,CEN,HOS} i {EST,UNI}, les arestes que creuen aquell tall són MER–UNI (6), RIO–CEN… no —RIO i CEN són al mateix costat—; el creuen MER–UNI (6), UNI–CEN (8) i ALM–EST (7): la mínima disponible passa a ser MER–UNI, i la propietat del tall la converteix en obligatòria. El MST només empitjora en la diferència 6 − 5 = 1.

Exercici 2:

Amb S = {IND}, les arestes que creuen el tall són totes les incidents a IND: EST–IND (9) i IND–HOS (6). La mínima és IND–HOS (6); per tant pertany a tot MST — sense executar res. La traça de Kruskal ho confirma (IND–HOS acceptada; EST–IND ni tan sols es considera abans de completar l'arbre). Aquest truc del "tall d'un sol node" dona gratis una aresta segura per cada vèrtex: la més barata de cada node sempre és al MST (amb pesos diferents).

Exercici 3:

Cada unió redueix el nombre de components en 1 (comencem amb n = 9); per això n'hi ha prou de comptar les acceptades. Els grups resultants són eloqüents: el nucli urbà densament connectat per una banda, i el Polígon i el Parc —les zones perifèriques de grau 2 que venim assenyalant des de 03-01— com a satèl·lits. Kruskal no només construeix xarxes: revela estructura.

El MST respon la pregunta d'infraestructura —connectar-ho tot al mínim cost total— i la seva solució voraç no és un cop de sort: la propietat del tall, demostrada per intercanvi, certifica que l'aresta més barata de qualsevol tall és obligatòria. Kruskal l'explota ordenant arestes i vigilant cicles amb l'union-find de 01-04 (segona llavor collida: les dues promeses d'aquella lliçó estan saldades); Prim l'explota fent créixer un arbre amb el mateix heap de Dijkstra però prioritzant el pes de l'aresta, no la distància acumulada. I hem delimitat amb un contraexemple allò que el MST no és: l'arbre de Dijkstra optimitza distàncies des d'un origen, el MST optimitza la suma — confondre'ls costaria a Rutalia un 24% en rases. Fins aquí, les nostres arestes mesuraven el cost de travessar-les. La propera lliçó els dona un significat nou: capacitat — quants paquets per hora caben per cada carrer. Amb això entrem en els problemes de flux màxim (03-05): quin és el cabal màxim de repartiment entre el magatzem i un barri en hora punta, i quin és el coll d'ampolla que el limita.