Tema 2. Fonaments i aplicacions de teoria de grafs. Diagrames en arbre.

Índex

1. Introducció
2. Concepte de graf: definicions i tipologia
3. El grau d'un vèrtex i el lema de l'apretó de mans
4. Representació de grafs: matrius i llistes
5. Connexió, camins i cicles. Grafos eulerians i hamiltonians
6. Planaritat, coloració i teorema dels quatre colors
7. Arbres: caracteritzacions i propietats
8. Arbres generadors i arbre generador mínim
9. Diagrames d'arbre: recompte i probabilitat
10. Algoritmes sobre grafs i panorma d'aplicacions
11. Aplicació didàctica i relació amb el currículum
12. Conclusió
13. Bibliografia i referències

1. Introducció

El 1707-1783 va enviar a l’Acadèmia de Ciències de Sant Petersburg una memòria breu, Solutio problematis ad geometriam situs pertinentis, dedicada a un passatemps que circulava entre els veïns de Königsberg. La ciutat, partida pel riu Pregel, tenia dues illes i set ponts, i la pregunta era si podia donar-se un passeig que creués cada pont exactament una vegada. Euler va demostrar que no, però el que és decisiu no va ser la resposta sinó el mètode: va descontentar al problema de tota la seva geometria —dàncies, formes, ribes — i es va quedar amb l'únic que decidia la qüestió, quatre masses de terra i les connexions entre elles. Aquest gest d'absificació va fundar alhora la teoria de grafs i, en germen, aquella «gomètrica de la posició» que Leibniz havia imaginat mig segle abans i que acabaria anomenant-se topologia.

Un graf és un objecte d'una senzillesa gairebé provocadora: una col·lecció de , i una col·lecció de , cadascuna de les quals unix dos vèrtexs. Res més. Sobre aquesta base mínima s'ha aixecat una de les teories més fèrtils de la matemàtica contemporània, i la raó és que moltíssimes situacions tenen exactament aquesta forma — objecte i relacions entre ells —: ciutats i carreteres, persones i amistats, pàgines web i enllaços, tasques i dependències, assignatures i coincidències d'horari. Veure un problema com un graf és, sovint, haver resolt a mitges.

El tema pertany de ple a la matemàtica discreta , la que compta amb nombres naturals en lloc de mesurar en un continu, i està emparentat de prop amb les tècniques de recompte que s'estudien a continuació en el temari. Aquesta propania explica el segon concepte del títol: els diagrames en arbre** * són l'aplicació de la teoria de grafs amb més presència real a les aules de Secundària, perquè són l'eina natural per enumerar de forma sistemàtica i per calcular probabilitats d'experiments compostos. El currículum vigent organitza els sabers de la matèria en sentits —numèric, de la mesura, espacial, algèbric, estocàstic i socioafectiu — i aquest tema irriga sobretot el* sentè estocàtic , on els diagrames d'arbre aparixen de forma explícita des dels primers cursos de l'etapa, i el assentit algèbric, que acull el pensament computacional.

El desenvolupament resseguix quatre mirades entrellaçades: la fundacional, que fixa amb rigor què és un graf, com es classifica i com es representa; la dels problemes clàssics que forjar la disciplina — Euler i Hamilton, la planaritat, els quatre colors —; la dels àrbols , la família més important en les aplicacions, amb les seves caracteritzacions, els seus arbres generadors mínims i els diagrames de l'aula; i la algorítmica i aplicada, que explica per què uns punts i unes línies sostenen avui els navegadors i l'estudi de les xarxes. Al llarg del camí s'estarà assenyalant, en cada bloc, amb què sabers connecta, quins errors troba el docent i amb quines situacions d'aprenentatge es porta a l'aula.

Figura 1. El plano de Königsberg reducido a lo esencial: cuatro vértices y siete aristas, dos de ellas paralelas a cada lado de la isla.

2. Concepte de graf: definicions i tipologia

2.1. Definició formal i vocabulari bàsic

Un graf és un parell G=(V,E) on V és un conjunt finit no buit els elements del qual són els o nodes, i E és un conjunt de , cadascuna d'elles determinada per un parell de vèrtexs. Si l'arribada unix u i v, es diu que u i v són els seus , que són adyacents i que l'aresta és amb ambdós; dues arestes amb un extrem comú són adjacents entre si. El número de vèrtexs |V| és el I el graf i el nombre d'arrestes |E|, el seu Llevat de menció expressa, es treballa amb grafs finits, que són els que interessen a les aplicacions i a l'aula.

Sota aquesta definició, s’amaga una decisió conceptual que convé subratllar des del principi: no és un dibuix. Dos diagrames d'aspecte molt diferent poden representar el matix gràfic, perquè l'únic que compta és quins vèrtexs estan units amb quins, no on es situen els punts ni si les línies es creuen en traçar- les. La distinció entre la estructura — les dades d'adyacència — i les seves infinites representacions gràfiques és una de les idees més formatives del tema i, alhora, la font de la preconcepció més tenaç de l'alumne, que atribuix significat a trets accidentals del dibuix, començant pels encreuaments.

2.2. Variants: multigrafs, dígrafs i grafs ponderats

Segons el que es permeti en E s'obté una tipologia que cal manejar amb precisió. Un graf simple no admet — aristes que unixen un vèrtex amb si matix — ni aristes múltiples o paral·leles entre el matix parell de vèrtexs; cada aresta és llavors un parell no ordenat \{u,v\} amb u\neq v. Un multigraf sí que admet arestes paral·leles, que és el que exigia Königsberg; si a més es permeten llaços es parla de pseudograf. Un graf dirigit o digraf substituix les arestes per arcs, parells ordenats (u,v): la relació adquirix sentit, d'origen a destí, i modelitza carrers de direcció única, enllaços web o precedències entre tasques. Un graf ponderat afegix una funció de 14o w:E\to\mathbb{R}, gairebé sempre positiva, que representa una distància, un cost, un temps o una capacitat; pràcticament tota aplicació logística treballa amb grafs ponderats.

2.3. Famílies amb nom propi, subgrafs i isomorfisme

Algunes famílies reaparixen tant que tenen nom propi. El graf complet K_n unix entre si tots els seus n vèrtexs i té per tant

Arestes, fórmula que connecta immediatament amb el recompte i que respon a la pregunta clàssica de quants apretons de mans es donen en un grup de ZPLHMATHIT31Z persones. El ** camí** P_n i el ** cicle** ZPLHMATHITZ són, respectivament, una successió oberta i una tancada de vèrtexs consecutius. Un graf és ** regular de grau k** si tots els seus vèrtexs tenen exactament k veïns. És ** 125partit** si els seus vèrtexs es repartixen en dos conjunts disjuntets de manera que tota aresta unix un vèrtex d'un amb un altre del segon, mai dos del matix costat; el ** 125partit complet** K_{m,n} conté totes les arestes possibles entre un grup de m i un altre de n vèrtexs. Els bibpartits modelitzen els aparellaments —persones i tasques, alumnes i projectes — i permeten una caracterització molt útil: un gràfic és bibret si i només si no conté cicles de longitud senar** *.

Un ** subgraf** de G s'obté prenent part dels seus vèrtexs i part de les seves arestes; si conserva tots els vèrtexs s'anomena subgraf generador o recobridor, noció imprescindible per l'apartat 8. Dos grafs són isomorfos ** quan hi ha una bijecció entre els seus vèrtexs que conserva les adyacències: són el matix gràfic amb altres etiquetes o dibuixat d'altra manera. Decidir amb eficiència si dos grafs són isomorfos ha resistit durant dècades a la classificació habitual de la complexitat, senyal que fins i tot les preguntes més elementals poden amagar una dificultat formidable. Finalment, el** graf complementari \overline{G} unix exactament els parells que en G no eren adjacents, de manera que ambdós es repartixen totes les arestes de K_n; moltes propietats s'aclarixen al mirar-lo, i en l'apartat 6 apareixerà un teorema profund enunciat en aquests termes.

3. El grau d'un vèrtex i el lema de l'apretó de mans

El rat d'un vèrtex v, que escriurem \operatorname{gr}(v), és el nombre d'arrestes incidents amb ell, amb el conveni que un llaç suma dos perquè incidix dues vegades. Es diuen grau mínim i grau màxim del graf, i es denoten \delta(G) i \Delta(G), el menor i el major d'aquests valors. Un vèrtex de grau 0 és i un de grau 1 és una, terme que resultarà central en parlar d'arbres. En un dígraf el grau es desdobla en rat d'entrada i grau de eixida, la suma total del qual coincidix en ambdós casos amb el nombre d'arcs.

El primer teorema de la teoria és també el més rendible en un examen, per la seva brevetat i per l'elegància de la seva demostració:

Llema de l'apretó de mans. En tot gràfic (o multigraf) G=(V,E) es complix \sum_{v\in V}\operatorname{gr}(v)=2\,|E|.

Demostració per doble comptat. Comptem de dues maneres el nombre de parells formats per una aresta i un dels seus extrems, és a dir, el nombre de Recorrent els vèrtexs, cada v aporta exactament \operatorname{gr}(v) incidències, i la suma total és el membre esquerre. Ressent les arestes, cadascuna aporta exactament dues incidències —sus dos extrems, o dues vegades el matix vèrtex si és un llaç —, i la suma total és 2|E|. Tots dos recomptes expliquen el matix, i després coincidixen. \blacksquare

La conseqüència immediata és el resultat que sol demanar-se a l'aula: el nombre de vèrtexs de grau senar és sempre parell** . En efecte, si la suma de tots els graus és parell i els vèrtexs de grau per aportar una quantitat parell, la suma dels graus senars restants ha de ser parell, el que obliga a que hi hagi una quantitat parell de sumands senars. D'aquí es deduixen sense esforç fets que semblen endevinalles: és impossible construir una xarxa en la qual exactament set ordinadors tinguin cadascun tres connexions, perquè hi hauria set vèrtexs de grau senar. És una excel·lent primera experiència de mostració per impossibilitat per tercer i quart de l'E. ESO: es rauen sobre tots els casos alhora, sense construir-ne cap.

La recessió de graus d'un gràfic és la llista dels graus dels seus vèrtexs ordenada de més gran a més petita. No tota successió de nombres naturals és realitzable: pel lema, la seva suma ha de ser parell, encara que aquesta condició no n'hi ha prou — la successió (3,3,3,1) suma parell i no correspon a cap graf simple —. L'algoritme de Havel-Hakimi decidix constructivament si una successió és, i el teorema d'Erdos-Gallai dóna una caracterització tancada mitjançant desigualtats.

Quan el graf descriu una xarxa del món real, el que és interessant deixa de ser cada grau i passa a ser la seva Réka Albert i Albert-László Barbàsi van descobrir a finals dels anys noranta que en moltes xarxes reals —enllaços web, xarxes de cites, xarxes metabòliques — aquesta distribució no es concentra al voltant d'una mitjana, com ocorreria si les connexions fossin aleatòries, sinó que seguix una llei potencial: Molts vèrtexs de grau baix i uns pocs concentradors de grau enorme. El model de creixement amb enganxament de preferència, en el qual els nous nodes es connecten amb més probabilitat als ja molt connectats, explica com emergix aquesta estructura i és avui el punt de partida de la ciència de xarxes.

Figura 2. Cada arista aporta dos incidencias, de modo que la suma de los grados duplica el tamaño del grafo; aquí hay además dos vértices de grado impar, nunca uno solo.

4. Representació de grafs: matrius i llistes

Per treballar amb un graf, i sobretot perquè el processi una màquina, cal escriure-ho sense dibuixar-lo. La matriu d'adyacència d'un graf amb vèrtexs numerats v_1,\dots,v_n és la matriu quadrada A d'ordre n l'element 1 si v_i i v_j són adjacents i 0 en cas contrari; en un multigraf s'anota directament el nombre d'arestes entre ambdós. Per a un graf no dirigit la matriu és, i si el graf és simple el seu diagonal és nul·la. La suma de cada fila és el grau del vèrtex corresponent, amb el que el lema de l'apretó de mans es releix com que la suma de tots els elements de A val 2|E|. En un dígraf la simetria es perd, i les sumes per files i per columnes donen els graus de eixida i d'entrada.

La matriu no és només un magatzem: és una eina de càlcul. Un resultat clàssic i molt vistos afirma que ** l'element (i,j) de la potència A^{k} compta exactament el nombre de recorreguts de longitud k que van de v_i a ZPLHMATH69Z**. La demostració és una inducció neta sobre k: el cas k=1 és la definició, i en el pas inductiu la regla del producte de matrius suma, sobre tots els vèrtexs intermedis, els recorreguts de longitud k-1 multiplicats per l'existència o no de l'arressió final. Així, l'àlgebra de matrius que l'alumne estudia al batxillerat adquirix un significat combinatori tangible.

Aquesta aliança entre matrius i grafs assolix una profunditat notable en la teeria espectral de grafs, que estudia què revela l'estructura d'un graf a partir dels valors propis de la seva matriu d'adyacència o de la seva matriu laplaciana. Fan Chung és l'autora del tractat de referència en aquesta matèria i una de les responsables que l'espectre es convertís en instrument habitual per mesurar la connectivitat i la velocitat amb què es difon la informació en una xarxa. En la mateixa línia algebraica se situa el teorema de Kirchhoff (1847), que compta els arbres generadors mitjançant un determinant i que retrobarem a l'apartat 8.

Davant de la matriu, la liista d'adyacència emmagatzema per a cada vèrtex la relació dels seus veïns. L'elecció entre ambdues no és cosmètica, i a l'aula servix per introduir el cost computacional amb un exemple palpable. La matriu ocupa sempre n^{2} posicions i respon en un sol pas si dos vèrtexs concrets són adjacents; la llista ocupa de l'ordre n+m posicions, on m és el nombre d'arestes, i permet recórrer els veïns d'un vèrtex sense examinar els altres. En un gràfic en la matriu és raonable; en un disperso , que és l'empleat a les xarxes reals — milions de persones de les que cadascuna conix a uns centenars —, seria inbordable i la llista és l'única opció sensat. A més, hi ha la matriu d'incidència, amb una fila per vèrtex i una columna per aresta, menys utilitzada en la pràctica però útil en el tractament algèbric.

Figura 3. Los dos dibujos comparten matriz de adyacencia y lista de vecinos: son el mismo grafo, y el cruce del segundo trazado no añade ningún vértice.

5. Connexió, camins i cicles. Grafos eulerians i hamiltonians

5.1. Recorreguts, connexió i distància

Un recorrit de u a v és una successió alternada de vèrtexs i arestes que comença en u, acaba en v i en la qual cada aresta unix els dos vèrtexs que la flanquegen. Si no repetix arestes, es diu o passeig; si a més no repetix vèrtexs, camí simple Un recorregut tancat que no repetix arestes és un , i si tampoc repetix vèrtexs excepte l'inicial, un cicle ; la d'un recorregut és el seu nombre d'arestes. Un graf és si entre cada parell de vèrtexs existix un camí, i en un altre cas es descompon de manera única en components connexes. La superfície entre dos vèrtexs és la longitud del camí més curt que els unix, i el, la major d'aquestes distàncies, mesura el compacta que és la xarxa. Un vèrtex la supressió del qual augmenta el nombre de components és un , un estudi de tall, i una aresta amb aquesta propietat, un ; ambdós identifiquen els punts fràgils d'una xarxa, i localitzar- los és el primer en avaluar la robustesa d'una infraestructura.

5.2. Grafos eulierians: la resposta de Königsberg

Un circuit culeriano recorre totes les arestes de la gràfica exactament una vegada i torna al punt de partida; si el recorregut no és tancat es parla de camí eulerià. El teorema que Euler va deixar plantejat i que Hierholzer va completar el 1873 es enuncia així:

Un multigraf connex admet un circuit eulerià si i només si tots els seus vèrtexs tenen grau parell, i admet un camí eulerià obert si i només si teniu exactament dos vèrtexs de grau senar, que seran forçosament els seus extrems.

La necessitat s'expressa a l'aula en un minut: cada vegada que el passeig entra en un vèrtex per una aresta ha de sortir per una altra de diferent, de manera que les arestes de cada vèrtex s'aparellin i el seu grau ha de ser parell; en el cas obert queden desemparejats el vèrtex de eixida i el d'arribada. La suficiència exigix un argument constructiu — pren un circuit qualsevol i, mentre quedin arestes sense usar, se li injeixi un altre que parteixi d'un vèrtex ja visitat —, essència de l'algoritme d'Hierholzer. En Königsberg, els quatre vèrtexs tenien un grau senar, amb el qual ni tan sols existia un camí obert: la resposta era doblement negativa.

Aquest teorema sosté els passatemps de "dibuixar sense aixecar el llapis", que a l'aula funcionen extraordinàriament bé: es repartixen figures, l'alumne descobrix per assaig quins es poden i quins no, i en comptar els vèrtexs senars el criteri aparix sol. És una tasca de baix llindar i sostre alt, accessible des de primer de l'escèrtic i prolongable fins a la demostració formal.

5.3. Grafos hamiltonians: un problema enganyosament semblant

Un cicle hamiltonià passa per tots els vèrtexs una vegada i torna a l'origen. El nom prové del joc* icosià* que William Rowan Hamilton va comercialitzar en 1857, un dodecaedre de fusta en què calia recórrer tots els vèrtexs. La definició s'assembla tant a l'anterior que l'alumnat —i no pocs opositors — les confon: la diferència està en si s'exgoten les o els, i convé dir-ho així de cru.

I no obstant això, el semblant és enganyós: no es conix cap caracterització senzilla dels grafs hamiltonians, i decidir si un graf ho és un problema NP-complet, computacionalment dur en el pitjor cas. Només es disposa de condicions suficients que exigixen abundància d'arestes: el teorema de Dirac (1952) garantix que si n\ge 3 i \delta(G)\ge n/2 el graf és hamiltonià, i el d'Ore (1960) el debilita demanant \operatorname{gr}(u)+\operatorname{gr}(v)\ge n per a cada parell de vèrtexs no adjacents. Cap de les dues és necessària: el cicle C_{10} és hamiltonià i té tots els graus iguals a 2. La investigació continua viva: Daniela Kühn i Deryk Osthus han demostrat en l'última dècada velles conjectures sobre la descomposició de grafs densos i regulars en cicles hamiltonians.

El contrast Euler-Hamilton merix exposar-se sempre, perquè és una de les primeres finestres honestes a la teoria de la complexitat: dues preguntes bessones, una amb criteri immediat i una altra sense criteri conegut. En la versió ponderada, la cerca del cicle hamiltonià més barat és el blema del viatjant, omnideArque en logística, en el traçat de circuits impresos i en la planificació de rutes de repartiment.

Figura 4. Dos grafos pequeños que separan con nitidez ambas nociones: el de la izquierda agota las aristas pero no admite ciclo hamiltoniano; el de la derecha lo admite y no tiene circuito euleriano.

6. Planaritat, coloració i teorema dels quatre colors

6.1. Grafos plànols i la fórmula d'Euler

Un graf és Si admet alguna representació en la que les arestes no es tallen excepte en els seus extrems. Que un dibuix tingui encreuaments no prova res: el graf pot ser pla i estar mal dibuixat, distinció en la qual convé insistir perquè enllaça amb la idea de l'apartat 2 . Un dibuix pla dividix el pla en regions o, comptant sempre l'exterior no acotada. La joia de l'apartat és la relació descoberta per Euler en 1750 per als poliedres i vàlida per a tot gràfic pla connex:

on ZPLHMATHITZ és el número de vèrtexs, A el d'arestes i C el de cares. La demostració per inducció sobre el nombre d'arrestes és assequible: si el graf no té cicles és un arbre, amb A=V-1 i una única cara, i la igualtat es complix; si té un cicle, en suprimir una de les seves arestes es perden una aresta i una cara i l'expressió no varia. Aplica-la als poliedres convexos —comptar cares, arestes i vèrtexs d'un cub o dodecaedre construïts amb cartolina — és un pont natural amb el sentit espacial del currículum i una de les activitats més agraïdes de tercer i quart de l'escàntic.

De la fórmula es deduixen cotes molt útils. En un gràfic pla simple amb V\ge 3, cada cara està vorejada per almenys tres arestes i cada aresta voreja al mull dues cares, el que dóna per doble comptat 2A\ge 3C i, substituint,

Si a més no teniu triangles — per exemple si és bibpartit —, cada cara necessita almenys quatre arestes i la cota s'afina a A\le 2V-4. Aquestes desigualtats són la manera més econòmica de demostrar que certs grafs no són plànols.

6.2. Les dues obstruccions: Kuratowski

El gràfic complet K_5 té V=5 i A=10, mentre que ZPLHMATHIT5Z: incomplix la cota i per tant no és pla. El bibpartit complet K_{3,3} té ZPLHMATHIT97Z i ZPLHMATHIT98Z, i al mancar de triangles hauria de complir ZPLHMATHITZ: tampoc ho és. Aquest segon cas és el cèlebre endevinalla de les tres cases que han de connectar-se als subministraments d'aigua, gas i electricitat sense que les conduccions es creuin: impossible, i ara se sap per què. El notable és que aquests dos grafs esgoten el problema: el teorema de Kuratowski (1930) afirma que un graf és pla si i només si no conté cap subdivisió de K_5 ni de K_{3,3}. Que una propietat geomètrica tan escorrida es redueixi a l'absència de dues configuracions concretes és un dels resultats més bonics de la teoria.

6.3. Coloració i els quatre colors

Colorejar ** un graf és assignar un color a cada vèrtex de manera que dos adjacents mai rebin el matix; el mínim nombre de colors necessari és el** número cromàtic \chi(G), que val 2 exactament quan el graf és bipartit i n en K_n. La formulació és abstracta, però els problemes que resol són quotidians: repartir assignatures en franges horàries sense que coincideixin dues d'un matix grup, assignar freqüències a antenes properes sense interferències o distribuir tasques entre recursos incompatibles.

Colorejar un mapa polític de manera que dos països fronterers rebin colors diferents equival a acolorir els vèrtexs del graf que té un vèrtex per país. El 1852 Francis Guhrie va conjupir que Quatre colors són prou sempre La història posterior és exemplar: Kempe va publicar el 1879 una demostració que la comunitat va donar per bon onze anys, fins que Heawood va trobar l'error el 1890; de l'argument trencat es va rescatar el teorema dels cinc colors, la demostració del qual sí és elemental i cap en una classe. L'anunci complet va resistir fins al 1976, quan Appel i Haken el van provar reduint el problema a un conjunt finit de configuracions inevitables i comprovant-les amb ordinador. Va ser la primera gran demostració assistida per màquina i va desaclarir un debat legítim sobre què és una demostració quan ningú pot verificar-la sencera; el 1997 es va simplificar i el 2005 Gonthier la va formalitzar completament en un assistent de proves.

La coloració encara és un terreny de recerca de primer nivell. Una fita recent és el fort dels grafs perfectes , conjecturat per Berge el 1961 i demostrat el 2002 per Maria Chudnovski al costat de Robertson, Seymour i Thomas: un graf és perfecte —en ell i en tots els seus subgrafs induïts el nombre cromàtic coincidix amb la mida del major camarilla — si i només si ni ell ni el seu complementari contenen un cicle senar induït de longitud almenys cinc. Serveix per mostrar a l'alumne que la matemàtica no és un edifici tancat al segle XIX, sinó una disciplina viva.

Figura 5. La fórmula de Euler comprobada sobre un dibujo plano y usada como cota para descartar la planaridad de los dos grafos que caracterizan la obstrucción.

7. Arbres: caracteritzacions i propietats

Entre tots els grafs, els ** Un lloc privilegiat, els ocupen un lloc privilegiat: són la frontera exacta entre la connexió i l'absència de cicles, l'estructura més econòmica capaç de mantenir unida una xarxa. Un** Un arbre ** és un graf connex i sense cicles; un graf sense cicles però no necessàriament connex és un** secció, i cada un dels seus components és un arbre.

7.1. Sis maneres equivalents de dir el matix

La riquesa del concepte s'aprecia en què admet diverses definicions equivalents. Per a un gràfic G amb n vèrtexs, les següents afirmacions diuen exactament el matix:

• G és connex i sense cicles.
• Entre cada parell de vèrtexs de G existix un únic camí simple.
• G és connex i té exactament ZPLHMATHI11Z arestes.
• G és acíclic i té exactament n-1 arestes.
• G és minimalment connex *és connex i al suprimir qualsevol aresta deixa de ser-ho, de manera que totes les seves arestes són ponts.
• G és Maximalment acíclic: és acíclic i en afegir qualsevol aresta entre dos vèrtexs no adjacents es crea exactament un cicle.

Ha de portar preparada almenys una de les implicacions. Que un arbre amb n vèrtexs tingui n-1 arestes es prova per inducció recolzant-se en un lema previ: tot arbre amb almenys dos vèrtexs té almenys dos fulls. Per veure-ho, pren-ho un camí simple de longitud màxima; els seus dos extrems han de tenir grau 1, perquè qualsevol aresta addicional en un extrem portaria a un vèrtex ja visitat —creant un cicle — o permetria allargar el camí, contra la maximalitat. Amb aquest lema la inducció és immediata: si n=1 hi ha 0 arestes; si ZPLHMATHID21Z, es poda un full amb la seva aresta, queda un arbre de n-1 vèrtexs que per hipòtesis té ZPLHMATHIDTZ arestes, i en retornar el full s'arriba a ZPLHMATHID24Z. Aquest argument de pota de fulles reaparix constantment.

7.2. Arbres amb arrel

Un arbre amb arrel és un arbre en el qual s'ha distingit un vèrtex, la raíz, el que orienta implícitament totes les arestes allunyant- se d'ella i induix un vocabulari familiar: el veí més proper a l'arrel és el del vèrtex i els restants són els seus; els vèrtexs sense fills són les i els altres, interns; el nivell d'un vèrtex és la seva distància a l'arrel, i la aça de l'arbre, el nivell màxim. Un Un binari binari és aquell en el qual cada vèrtex té al màxim dos fills, i sobre ell es construixen els mètodes de recerca i ordenació de dades més habituals. L'observació clau és que un arbre binari d'alçada h té al mum ZPLHMATHI12Z vèrtexs, de manera que un equilibrat arriba a un nombre enorme de fulls amb molt pocs nivells: és la raó matemàtica de que cercar en una llista ordenada d'un milió d'entrades exigeixi unes vint comparacions i no un milió.

7.3. Quants arbres hi ha

Comptar arbres conduix a una de les fórmules més sorprenents de la combinatòria. La fórmula de Cayley (1889) afirma que el nombre d'arbres diferents que es poden construir sobre n vèrtexs etiquetats és

Amb quatre vèrtexs surten 4^{2}=16 arbres i amb deu, mil milions. La demostració més elegant, deguda a Prüfer, establix una bijecció entre els arbres etiquetats i les successions de ZPLHMATHIDZ etiquetes: un exemple esplèndid de la tècnica de comptar un conjunt posant-lo en correspondència amb un altre que ja se sap comptar.

Figura 6. Un árbol con raíz con su vocabulario jerárquico; nótese la relación entre el número de vértices y el de aristas, que caracteriza a todo árbol.

8. Arbres generadors i arbre generador mínim

Un Un generador de control d'un gràfic connex G és un subgraf que conté tots els seus vèrtexs i que és un arbre. Sempre hi ha una badalla, esborreu arestes de cicles fins que no en quedi cap, i en general no és únic: això és justament el que explica el teorema de Kirchhoff. Interpretat sobre una xarxa, un arbre generador és la selecció d'enllaços més econòmica que manté tot connectat: exactament n-1 connexions, sense bucles.

Aquesta lectura té una conseqüència pràctica de primer ordre en les xarxes de comunicacions. Quan diversos commutadors es connecten formant cicles, un missatge difós circularia indefinidament i col·lapsaria la xarxa. La solució que Radia Perlman va idear el 1985, convertida després en el protocol de l'arbre d'expansió i en base de l'estàndard IEEEE 802.1D, consistix en que els commutadors calculin entre tots, de forma distribuïda, un arbre generador de la xarxa i desactivin lògicament les connexions sobrants, deixant-les com a reserva per si falla un enllaç. És una de les traduccions més directes d'un teorema de grafs a una infraestructura d'ús diari.

8.1. L'arbre generador mínim

Si el graf és, la pregunta s'afina: entre tots els seus arbres generadors, quina té la suma de pesos més petita? Aquest és el Un generador mínim, i el seu enunciat modelitza sense retocs un problema d'enginyeria recurrent: tendir el cablejat elèctric, la fibra òptica o la xarxa de reg que connecti un conjunt de punts amb la menor longitud total. No és casual que el primer algorisme conegut el publiqués Otakar Boruvka el 1926 amb una motivació aplicada: electrificar Moravia gastant el mínim de cable. Aquest origen convertix el tema en una ocasió honesta —no decorativa — per parlar de eficiència en l'ús dels recursos , perquè minimitzar material i obra civil és alhora estalvi econòmic i menor impacte ambiental, en la línia dels objectius de desenvolupament sostenible sobre infraestructures resilients i consum responsable ( ODS 9 i ODS 12 ) .

8.2. Dos algorismes voravies

El Algoritme de Kruskal (1956) ordena totes les arestes de menor a major pes i les va acceptant una a una, descartant aquelles que tancarien un cicle amb les ja elegides; acaba quan ha acceptat ZPLHMATH132Z arestes. El Algoritme de Prim (1957, anticipat per Jarník el 1930) fa créixer en canvi un únic arbre: part d'un vèrtex qualsevol i en cada pas afegix l'arrestida més barata que unix el ja construït amb un vèrtex encara fora.

Tots dos són vorces: En cada pas prenen la decisió localment millor sense reconsiderar-la mai. Que una estratègia tan miop assoleixi l'enorme global és sorprenent i necessita demostració; la clau és la ropietat de tall, segons la qual, donada qualsevol partició dels vèrtexs en dos blocs, l'arressió de menor pes que els unix pertany a algun arbre generador mínim. Afegeix-la a un arbre òptim que no la contingués crearia un cicle del qual podria retirar-se una altra aresta del matix tall, obtenint un arbre de pes menor o igual: el clàssic argument d'intercanvi. L'arbre mínim és unic si tots els pesos són diferents, però pot no ser-ho si hi ha empats. Pel que fa al cost, Kruskal treballa a O(|E|\log|E|), dominat per l'ordenació, i Prim en ZPLHMATHIS34Z amb una cua de prioritat.

Hi ha un error de comprensió molt estès que convé anticipar a l'aula: l'arbre generador mínim no conté, en general, el camí més curt entre dos vèrtexs donats. Optimitza el cost total de la xarxa, no cada trajecte; per això cal un altre algorisme, que es veu més endavant. Presentar els dos problemes seguits i contrastar-los evita una confusió molt estesa.

Figura 7. Kruskal acepta las aristas por orden creciente de peso y descarta las que cerrarían un ciclo; se detiene al reunir una arista menos que vértices tiene el grafo.

9. Diagrames d'arbre: recompte i probabilitat

Arribem al segon concepte del títol, el de major presència real a les aules. Un diagram en arbre és, senzillament, un arbre arrel que desplega de forma ordenada totes les possibilitats d'un procés que passa per De l'arrel surten tantes branques com opcions tingui la primera etapa; de cadascuna, les de la segona, i així successivament. Cada és un resultat possible i cada camí de l'arrel a un full, la seqüència de decisions que el produix. El seu valor didàctic està en que El procés: el que en una fórmula queda ocult, en l'arbre es veu.

9.1. Comptar per etapes

El nombre de fulls és el producte de les opcions de cada etapa, de manera que el diagrama és la representació visual del principi de multiplicació. Per formar números de dues xifres diferents amb els dígits 1, 2 i 3, l'arbre té tres branques inicials i dos des de cada una, és a dir 3\cdot 2=6 fulls: ZPLHMATHI13Z, ZPLHMATH140Z, 21, ZPLHMATHISZ, 31 i 32. Si es permet repetir xifra, cada nivell tindria tres branques i sortirien 3^{2}=9.

Aquest contrast, dibuixat amb els dos arbres un al costat de l'altre, resol la confusió més persistent del bloc de recompte: la de si importa l'ordre i si es pot repetir . Qui ha construït l'arbre no necessita recordar quina fórmula correspon a cada cas, perquè pot reconstruir-la: veu que al no repetir el nombre de branques disminuix i aparix el factorial, i que en repetir es manté constant i aparix la potència. Per això el diagrama ha de precedir a la fórmula i no a l'inrevés; això és, a més, un recurs de Per a l'aprenentatge** , perquè oferix una via visual a qui no accedix amb comoditat al llenguatge simbòlic, sense rebaixar l'exigència matemàtica.

9.2. Probabilitat d'experiments compostos

La potència del diagrama es multiplica al etiquetar cada branca amb la seva probabilitat Dues regles resolen llavors gairebé qualsevol problema d'experiment compost. La regla del producte diu que la probabilitat d'un camí complet és el producte de les probabilitats de les seves branques, i en les etapes posteriors aquestes probabilitats són ja pel que ha passat abans, de manera que l'arbre incorpora la condicionalitat sense necessitat de nomenar-la:

La continua de la suma diu que la probabilitat d'un succés assolible per diversos camins diferents és la suma de les probabilitats d'aquests camins. Convé exigir sempre una comprovació que detecta la majoria dels errors: les probabilitats de les branques que surten d'un matix node han de sumar 1, i també la suma de tots els fulls.

Ens hem de considerar una urna amb tres boles vermelles i dos blaus de la que s'extreguin dos sense substitució. En la segona etapa les probabilitats canvien, perquè queda una bola menys i la composició depèn de l'alliberat abans. La probabilitat de treure exactament una bola vermella és la suma dels dos camins mixtos:

El matix diagrama admet una lectura a la fi de la probabilitat que tanqui una de les idees més fines. Preguntar-se, sabent que la segona bola va ser blava, quina és la probabilitat que la primera fos vermella invertix el sentit natural de l'arbre i conduix al : es dividix la probabilitat del camí favorable entre la suma de tots els camins compatibles amb l'observat. Que aquest raonament, que en el batxillerat es formalitza i sustenta des del diagnòstic mèdic fins als filtres de correu, podeu entendre's abans com un simple recorregut de branques en sentit invers és el millor argument per ensenyar bé els diagrames en arbre.

9.3. La mateixa estructura, a tot arreu

El diagrama en arbre és només la cara més escolar d'una idea universal. Els arbres de decisió organitzen diagnòstics i classificacions i són un pilar de l'aprenentatge automàtic; els arbres de joc descriuen les jugades de l'escacs i sostenen l'estratègia minimax; els arbres sintàctics representen l'estructura d'una frase o d'un programa; els àrbols de Huffman comprimixen fitxers assignant codis més curts als símbols més freqüents. En tots llau la mateixa estructura arran que l'alumne maneja amb les boles d'una urna, i assenyalar-ho en classe mostra que un concepte elemental ben comprès obre la porta a les idees més avançades.

Figura 8. Cada camino se recorre multiplicando y cada suceso se calcula sumando caminos; la comprobación de que el total vale la unidad detecta casi todos los errores.

10. Algoritmes sobre grafs i panorma d'aplicacions

Si la teoria de grafs ha passat de curiositat decimonònica a eina imprescindible, és pels seus Algorismes, capaços de respondre preguntes sobre grafs gegants en fraccions de segon. Portar-los a l'aula és a més l'ocasió més natural per desenvolupar el pensar computacional que el currículum vigent incorpora al sentit algèbric, perquè permet passar del raonament en paper a la programació d'un procediment sense canviar de problema.

Els dos recorreguts bàsics són la en amplada i la fúsqueda en profunditat . La primera explora el graf per capes —primeixo els veïns del vèrtex de partida, després els veïns d'aquests—, s'ocupa amb una cua i proporciona de regal els camins més curts en nombre d'arrestes, el que la fa idònia per resoldre laberints o mesurar graus de separació en una xarxa social. La segona avança tot el que pot per una branca abans de retrocedir, s'implementa amb una pila o amb recursió, i és la base de la detecció de cicles, de la identificació de components i de l'ordenació topològica de tasques amb precedències. Ambdues recorren el gràfic en temps O(|V|+|E|), proporcional a la mida de l'entrada.

Quan les arestes tenen pesos, el camí amb menys arestes deixa de ser el més barat i cal el Algoritme de Dijkstra (1959), que manté una frontera de vèrtexs amb la millor distància provisional coneguda i en cada pas tanca definitivament el més proper a l'origen. També és una mica de pols, i la seva correcció depèn d'una hipòtesi que s'ha d'enunciar sempre: els pesos no poden ser negatius; si n'hi ha, es recorre a l'algoritme de Bellman-Ford. Dijkstra, juntament amb els refinaments que orienten la recerca cap al destí en comptes d'expandir-la en totes direccions, és el que executa un navegador cada vegada que calcula una ruta, i explicar-ho així en classe convertix una llista de passos abstracta en alguna cosa que l'alumne porta a la butxaca.

El panorama d'aplicacions desborda qualsevol enumeració, però convé portar mitja dotzena d'exemples sòlids. A internet, l'algorisme que va ordenar els primers cercadors interpretava els enllaços entre pàgines com a vots i calculava la importància de cadascuna mitjançant el vector propi dominant d'una matriu associada al gràfic: àlgebra lineal i grafis una altra vegada de la mà. A xarxes socials s'estudien la centralitat, la formació de comunitats i la propagació de rumors. En logística conviuen el problema del viatjant i el del carter xinès, que busca el recorregut més curt que passi per totes les arestes i que, a diferència de l'anterior, sí té solució eficient recolzant-se en el teorema d'Euler. En planificació de projectes, les tècniques de camí crític calculen sobre un gràfic dirigit acíclic la durada mínima d'una obra. En biologia, els arbres filogenètics reconstruyen el parentiu entre espècies. I fins i tot l'assignació de torns, aules o tribunals es resol com una coloració o com un aparellament en un graf bipartit.

11. Aplicació didàctica i relació amb el currículum

Els eixos didàctics s'han anat teixint al llarg del desenvolupament; convé consolidar-los aquí amb la vista posada en la pràctica d'aula.

L'ancoratge curricular més ferm està en el ** assentit estocàstic**, que recull de manera explícita els diagrames d'arbre com a tècnica de set per sis anys en els primers cursos de l'ESO i com a eina per al càlcul de provabilitats d'experiments compostos ** en els últims, amb continuïtat en el batxillerat a través de la probabilitat condicionada i el teorema de Bays. Un segon ancoratge està en el** [sentit algèbric , que acull el pensament computacional : els recorreguts, el camí mínim i l'arbre generador són contextos idonis per introduir l'agoritmia. El tema irriga a més el sentit ** — la fórmula d'Euler sobre poliedres —, el de les** ** i el** Quant a les ** competències específiques**, la ** modelització** és aquí la reina, perquè traduir un mapa, una xarxa o un torneig a un gràfic és el gest essencial del tema; el Es troba un exemple curt i elegant — el lema de l'apretó de mans, les caracteritzacions de l'arbre, la impossibilitat de Königsberg —; i la ** Comunicació** s'exercita en justificar per què una ruta no existix.

L'experiència docent ha identificat errors i preconcepcions freqüents el coneixement de les quals permet intervenir abans que es consolidin. El més profund és confondre el graf amb el seu dibuix: creure que dues representacions diferents són grafis diferents, o que un encreuament del traçat és un vèrtex. Li seguixen comptar malament el grau quan hi ha un llaç, confondre el recorregut eulerià amb l'hamiltonià i suposar que l'arbre generador mínim conté el camí més curt entre dos punts. En els diagrames en arbre els ensopegades són d'altres: no ser sistemàtic i perdre branques, sumar quan s'han de multiplicar, no advertir que les probabilitats de la segona etapa canvien si l'extracció és sense reemplaçar, i oblidar comprovar que les branques d'un matix node en sumen un. Provocar deliberadament aquests errors amb un contraemplament és més eficaç que corregir-los després.

Metodològicament, el tema es presta com pocs al aprenentatge basat en problemes i projectes. Una puntuació d'aprenentatge de bon rendiment per als últims cursos de l'ESO és la xarxa de fibra d'una localitat: l'alumnat modelitza els carrers com un graf ponderat amb distàncies preses d'un pla real, aplica Kruskal per dissenyar l'estesa de cost mínim i discuti després què s'optima i què se sacrifica, el que enllaça de forma natural amb l'ús responsable dels recursos. Altres propostes d'alt rendiment són el clàssic "Es pot dibuixar sense aixecar el llapis?", la coloració d'un mapa real en col·laboració amb Geografia i el disseny d'un torneig d'aula, que és literalment un gràfic complet. La avaluació ha de ser coherent: juntament amb la prova escrita, observació del treball de modelització, portafoli del procés i rúbriques que valorin el raonament i la comunicació tant com el resultat.

Quant a la atenció a la diversitat, el tema té una virtut poc comuna: el seu llindar d'entrada és baixíssim — dibuixar punts i línies — i el seu sostre, altíssim, el que permet plantejar una mateixa tasca amb diversos nivells de repte sense segregar al grup, que és el cor del [Disseny universal per a l'aprenentatge . Convé presentar cada idea per més d'una via —manipulativa amb cordes i xinxetes, gràfica, simbòlica i digital —, perquè l'alumne amb dificultats en el càlcul pot rendir aquí a alt nivell: raonar sobre grafs amb prou feines exigix destresa aritmètica.

Mereix menció a part el sociograma, desenvolupat en els anys trenta per Jacob Moreno i Helen Hall Jennings, que representa com un gràfic dirigit les relacions d'alegència i rebuig dins d'un grup. És una eina valuosa de tutoria i convivència per detectar lideratges, subgrups i, sobretot, alumnat en risc d'aïllament: els vèrtexs de grau d'entrada nul són exactament els que cal mirar. Que la mateixa estructura del tema serveixi per cuidar el clima de l'aula permet treballar el sentit socioafectiu i mostrar que les matemàtiques també servixen per mirar a les persones.

12. Conclusió

Recorre la teoria de grafs és assistir, en poc més de dos segles i mig, al recorregut complet d'una idea matemàtica: d'un passatemps sobre set ponts al llenguatge amb el qual avui es descriuen les xarxes de comunicació, la logística mundial i el funcionament d'una cèl·lula. Pel camí hem fixat els fonaments —què és un graf, com es classifica, com es representa i quina governa la seva estructura a través del grau —, hem reviscut els grans problemes clàssics — Euler i Hamilton, la planaritat, els quatre colors —, hem estudiat amb detall els , aquesta frontera exacta entre la connexió i l'aclicitat, i hem desplegat els que enllacen el tema amb el recompte i la probabilitat de l'aula.

El valor formatiu d'aquest contingut no residix només en els teoremes, sinó en quatre idees transversals que el docent ha de fer visibles: la la potència de la modelització, ja que bona part del treball consistix a saber mirar un problema com un graf; la distinció entre la estructura i les seves representacions, lliçó d'abstracció aplicable molt més enllà d'aquest tema; el contrast entre el fàcil i el difícil — el criteri immediat d'Euler davant de la duresa del problema de Hamilton, l'arbre mínim davant del viatjant —, primera finestra honesta a la teoria de la complexitat; i la constatació que la disciplina seguix viva, amb teoremes de primer ordre demostrats en les últimes dues dècades. Dominar el tema amb rigor i saber transposar-lo a l'aula amb sensibilitat cap a la diversitat i cap a l'entorn permet presentar, davant del tribunal i després davant de l'alumne, no una col·lecció de definicions, sinó el relat de com uns punts i unes línies es van convertir en una de les eines més poderoses per comprendre el món.

13. Bibliografia i referències

(a) Referències tècniques i científiques

• Euler, L. (1736). "Solut problematis ad geometriam situs pertinentis". Commentarii Acadèmiae Scientiarum Petropolitanae, 8, 128-140.
• Biggs, N., Lloyd, E. i Wilson, R. (1976). Graph Theory, 1736-936. Clarenden Press.
• Bondy, J. A. i Murty, U. S. R. (2008). Graph Theory. Springer.
• Diestel, R. (2017). Graph Theory (5.a ed). Springer.
• Wilson, R. J. (1996). Introduction to Graph Theory (4.a ed.). Longman.
• Grimaldi, R. P. (1997). Matemàtica discreta i combinatòria. Addison-Wesley Iberoamericana.
• García Meryo, F. (2005). Matemàtica discreta. Thomson- Paraninfo.
• Chung, F. R. K. (1997). Spectral Graph Theory. American Mathematical Society.
• Chudnovski, M., Robertson, N., Seymour, P. i Thomas, R. (2006). "The strong perfect graph theorem". Annals of Mathematics, 164( 1), 51-229.
• Barbàsi, A. - L. i Albert, R. (1999). « Emergeix of scàling in random networks». Science, 286( 5439), 509-512.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L. i Stein, C. (2022). Introduction to Algorithms (4.a ed.). MIT Press.
• Perlman, R. (985). "An algorithm for distributed computation of a spanning tree in an extend LAN". ACM SIGCOMM Computer Communication Review, 15( 4), 44-53.
• IEEE 802.1D. Media Access Control Bridges. Institute of Electrical and Electronics Engineers.
• Gardner, M. (Vaig dir). Circ matemàtic. Aliança Editorial.

(b) Recursos i webgrafia

• Institut GeoGebra: construccions interactives de grafs, recorreguts eulerians i diagrames en arbre.
• Federació Espanyola de Societats de Professors de Matemàtiques: monogràfics de matemàtica discreta i de probabilitat en Secundària a la revista Suma.
• Societat Espanyola de Recerca en Educació Matemàtica: actes amb investigacions sobre errors de l'alumne en probabilitat i recompte.
• NRICH, Universitat de Cambridge: col·lecció de tasques de sota llindar i sostre alt sobre grafs, recorreguts i coloració.
• Projecte Divulgamat, Reial Societat Matemàtica Espanyola: materials d'història de les matemàtiques i del problema dels quatre colors.

Orientacions per a l'estudi

• Obriu amb Königsberg i tanqueu el cercle amb el criteri d'Euler: és el fil narratiu que dóna unitat al tema i el tribunal ho agraix. Enuncieu la condició amb precisió —circuit si tots els graus són parells, camí obert si hi ha exactament dos senars — i expliqui en dues frases per què és necessària.
• Porti el lema de l'apretó de mans amb la seva demostració per doble comptatig escrita i assajada: és curta, elegant, s'exposa en tres minuts i demostra soltesa amb la tècnica de comptar el matix de dues maneres. Remola' l amb el corolari dels vèrtexs de grau senar.
• Noteu gaire preparat el has trobat Euler davant de Hamilton. És el punt on més es distingix a qui ha comprès el tema de qui l'ha memoritzat: matix aire, dificultat oposada, i una primera porta a la complexitat computacional.
• Memoritzi les caracteritzacions equivalents de l'arbre i sàpiga demostrar la de les n-1 arestes per poda de fulles. és el concepte que dóna títol al tema juntament amb els diagrames, així que no pot quedar en una definició solta.
• Prepareu un exemple petit de Kruskal resolt pas a pas, amb la llista d'arestes ordenada i les descartades marcades. Ocupa poc, es dibuixa ràpid i val més que mitja pàgina de prosa. En referència a Prim, el caràcter de la vora, la propietat de tall i la dada de Boruvka electrificant Moravia el 1926.
• Dediceu temps real als migagrames en arbre: és el contingut amb presència curricular més directa i el que un tribunal espera veure ben resolt. Porteu un exemple de probabilitat Amb i sense substitució, les regles del producte i de la suma, i la lectura inversa que conduix a Bayes.
• No es perdi enumerant aplicacions. Mitja dotzena ben elegides i explicades en una línia renden més que una llista de vint: navegador i camí mínim, cercador i enllaços, sociograma, carter xinès, filogènia i assignació d'horaris per coloració.
• A la part no es limiti a dir que el tema és motivador. Nom una situació d'aprenentatge concreta amb el seu curs, dos o tres errors freqüents de l'alumnat —el gràfic no és el seu dibuix, sumar davant de multiplicar probabilitats, l'arbre mínim no dóna el camí més curt — i una idea d'avaluació. És la part que més separa un notable d'un excel·lent i la que menys gent prepara.
• Reserveu entre cinc i vuit minuts finals per al tancament. Un tema que es queda sense conclusió per mala gestió del temps perd punts que ja estaven guanyats: cronomestre almenys dos assajos complets.
• Dibuixa les figures a mà mentre estudia, no només les miri. A l'examen s'escriuen amb pressa i sota pressió, i un gràfic mal traçat o un arbre tortit resten llegibilitat a un contingut correcte.