Grafs i arbres: graus, connectivitat, Euler, bipartició i planaritat

Un graf és el model matemàtic més versàtil que hi ha: serveix per a xarxes de carreteres, circuits, dependències entre tasques, relacions socials, molècules i estructures de dades. Això és alhora la seva força i el seu perill, perquè convida a raonar «amb el dibuix» en comptes de demostrar. Aquesta pàgina fixa el llenguatge i els resultats que sí que es poden invocar.

Llenguatge i representacions

Un graf simple no dirigit consta d'un conjunt de vèrtexs i un d'arestes, que són parelles no ordenades de vèrtexs diferents. Un multigraf admet arestes paral·leles; els llaços necessiten convencions pròpies (normalment compten doble al grau). En un digraf les arestes tenen sentit, i en un graf ponderat porten un cost.

El grau d'un vèrtex és el nombre d'arestes que hi incideixen. El resultat més bàsic de tota la teoria és el lema de les encaixades:

$$\sum_{v\in V} d(v) = 2|E|,$$

perquè cada aresta aporta $1$ al grau de cadascun dels seus dos extrems. Té una conseqüència immediata i molt útil: el nombre de vèrtexs de grau senar és parell, ja que la suma total ha de ser parella.

Sobre representacions: una matriu d'adjacència ocupa espai proporcional al quadrat del nombre de vèrtexs, i una llista d'adjacència ocupa espai proporcional a vèrtexs més arestes. Per a grafs dispersos, que són la majoria dels reals, la diferència és enorme i condiciona el cost de tots els algorismes.

Un camí simple no repeteix vèrtexs; un cicle tanca un camí sense repetir-ne els altres. Un graf és connex si qualsevol parella de vèrtexs es pot unir. Un arbre és connex i sense cicles; un bosc és qualsevol graf sense cicles.

La caracterització dels arbres

Val la pena veure per què, perquè els arguments es reutilitzen. Que la connectivitat doni almenys un camí és la definició; que n'hi hagi dos de diferents permetria construir un cicle ajuntant-los, cosa que contradiu la definició d'arbre.

Per al recompte d'arestes: en un arbre amb almenys dos vèrtexs, un extrem d'un camí simple de longitud màxima ha de ser una fulla (si tingués un altre veí, o bé allargaries el camí o bé tancaries un cicle). Eliminant aquesta fulla i la seva aresta queda un arbre amb un vèrtex menys, i per inducció surt que hi ha $n-1$ arestes.

I en sentit contrari: si un graf connex amb $n-1$ arestes tingués un cicle, podries treure'n una aresta mantenint la connectivitat, i quedaria un graf connex amb $n-2$ arestes, cosa impossible perquè connectar $n$ vèrtexs en necessita com a mínim $n-1$.

Euler, bipartició i planaritat

Un recorregut eulerià fa servir totes les arestes exactament una vegada. Amb totes les arestes dins d'una sola component connexa:

• Hi ha circuit eulerià (tancat) si i només si tots els graus són parells.
• Hi ha recorregut eulerià obert si i només si hi ha exactament dos vèrtexs de grau senar, i llavors són els extrems.

La necessitat és fàcil: cada vegada que passes per un vèrtex intermedi hi entres i en surts, cosa que consumeix dues arestes. La suficiència es construeix amb l'algorisme de Hierholzer, ajuntant circuits.

Un graf és bipartit si els vèrtexs es poden partir en dos grups de manera que tota aresta uneixi els dos grups. La caracterització útil és: és bipartit si i només si no conté cap cicle de longitud senar. A la pràctica es comprova amb una cerca per amplada assignant dos colors alternats; si trobes un conflicte, has detectat un cicle senar.

Per a un graf connex dibuixat al pla sense encreuaments, la fórmula d'Euler diu

$$|V| - |E| + |F| = 2,$$

comptant la cara exterior. D'aquí surten dues cotes molt útils: per a un graf simple planar amb almenys $3$ vèrtexs, $|E|\leq 3|V|-6$; i si a més és bipartit, $|E|\leq 2|V|-4$, perquè sense cicles de longitud $3$ cada cara necessita almenys quatre arestes.

Exercici resolt: fulles d'un arbre

Un arbre té quatre vèrtexs de grau $3$ i tots els altres de grau $1$. Quantes fulles té?

Sigui $\ell$ el nombre de fulles. El total de vèrtexs és $n = 4 + \ell$, i com que és un arbre té $n - 1 = 3 + \ell$ arestes.

Ara el lema de les encaixades:

$$4\cdot 3 + \ell\cdot 1 = 2(3+\ell) \quad\Longrightarrow\quad 12 + \ell = 6 + 2\ell \quad\Longrightarrow\quad \ell = 6.$$

L'arbre té $6$ fulles, $10$ vèrtexs en total i $9$ arestes.

Comprovació: suma de graus $= 12 + 6 = 18 = 2\cdot 9$. Correcte.

Exercici resolt: es pot recórrer sense aixecar el llapis?

Un graf té graus $4$, $4$, $3$, $3$ i $2$. Es pot dibuixar recorrent cada aresta exactament una vegada?

Comptem els graus senars: n'hi ha exactament dos (els dos de grau $3$).

Per tant, si el graf és connex, hi ha un recorregut eulerià obert, i ha de començar en un dels vèrtexs de grau senar i acabar a l'altre. No hi ha circuit tancat.

El nombre d'arestes: la suma de graus és $4+4+3+3+2 = 16$, o sigui $8$ arestes, i el recorregut en farà exactament $8$ passos.

Variants. Si tots els graus fossin parells, hi hauria circuit tancat i podries començar on volguessis. Si hi hagués quatre vèrtexs de grau senar, caldrien dos traços com a mínim, perquè cada traç només pot «gastar» dos extrems senars.