T57. Grafs. Aplicacions

Desarrollo del tema

# GRAFS. CONCEPTES BÀSICS I APLICACIONS

## 1. Introducció

La **teoria de grafs** estudia estructures formades per objectes i les relacions entre ells. És un llenguatge natural per modelar xarxes: carreteres, comunicacions, connexions socials, circuits elèctrics, dependències en projectes o en programació.

Un **graf** és una abstracció potent: amb pocs conceptes es poden resoldre problemes d'optimització i de connectivitat de gran interès didàctic i aplicat.

## 2. Definicions i terminologia

### 2.1 Graf simple

Un graf (no dirigit) es defineix com $G=(V,E)$, on: - $V$ és el conjunt de **vèrtexs** (o nodes) - $E$ és el conjunt d'**arestes** (parelles no ordenades de vèrtexs)

En un **graf simple** no hi ha llaços (arestes d'un vèrtex amb si mateix) ni arestes múltiples.

### 2.2 Graf dirigit (dígraf)

En un dígraf, les arestes són **arcs** ordenats $(u,v)$.

- **Grau sortint** $d^+(v)$: arcs que surten de $v$ - **Grau entrant** $d^-(v)$: arcs que entren a $v$

### 2.3 Graf ponderat

Un graf és **ponderat** si a cada aresta se li assigna un pes $w(e)$ (distància, cost, temps...).

### 2.4 Grau d'un vèrtex

En un graf no dirigit, el **grau** d'un vèrtex $v$ és el nombre d'arestes incidentes: $$d(v)=\#\{e\in E: v\in e\}$$

**Lema de les encaixades (handshaking):** $$\sum_{v\in V} d(v)=2|E|$$

Conseqüència: el nombre de vèrtexs de grau imparell és parell.

### 2.5 Subgrafs, camins i cicles

- **Camí:** seqüència de vèrtexs $v_0,v_1,\ldots,v_k$ amb arestes consecutives. - **Longitud:** nombre d'arestes $k$. - **Cicle:** camí tancat amb $v_0=v_k$ i sense repetir arestes (i, en graf simple, sense repetir vèrtexs excepte el primer/últim). - **Camí simple:** no repeteix vèrtexs.

### 2.6 Connexió

Un graf és **connex** si per a qualsevol parella de vèrtexs existeix un camí que els uneixi.

Les **components connexes** són els subgrafs connexos màxims.

## 3. Representacions de grafs

### 3.1 Matriu d'adjacència

Si $|V|=n$, la matriu $A=[a_{ij}]$ amb: $$a_{ij}=\begin{cases}1 & \text{si hi ha aresta entre } i \text{ i } j\\ 0 & \text{altrament}\end{cases}$$

En grafs no dirigits, $A$ és simètrica.

### 3.2 Matriu d'incidència

Matriu $B$ de mida $n\times m$ (vèrtexs × arestes) amb entrades 0/1 (o -1/1 en dígrafs).

### 3.3 Llistes d'adjacència

Estructura de dades molt eficient per a grafs esparsos: per a cada vèrtex, llista de veïns.

## 4. Tipus de grafs especials

- **Graf complet** $K_n$: tots els parells de vèrtexs connectats, $|E|=\binom{n}{2}$. - **Graf bipartit**: $V=U\cup W$ i les arestes uneixen un vèrtex d'$U$ amb un de $W$. - **Graf bipartit complet** $K_{m,n}$. - **Arbre**: graf connex sense cicles.

## 5. Arbres

### 5.1 Caracteritzacions equivalents

Per a un graf amb $n$ vèrtexs, són equivalents: 1. És un arbre. 2. És connex i té $n-1$ arestes. 3. És acíclic i té $n-1$ arestes. 4. Entre qualsevol parella de vèrtexs hi ha un únic camí simple.

### 5.2 Arbre d'expansió

En un graf connex, un **arbre d'expansió** (spanning tree) és un subgraf que és arbre i conté tots els vèrtexs.

En grafs ponderats interessa l'**arbre d'expansió mínim (MST)**.

### 5.3 Algorismes MST

- **Kruskal:** ordenar arestes per pes creixent i afegir-les si no creen cicles. - **Prim:** començar en un vèrtex i anar afegint l'aresta mínima que connecta un nou vèrtex.

Aplicacions: disseny de xarxes amb cost mínim (cablejat, canonades, carreteres).

## 6. Camins eulerians i hamiltonians

### 6.1 Eulerià

Un **camí eulerià** recorre totes les arestes exactament una vegada.

**Teorema d'Euler (graf connex):** - Té **circuit eulerià** (tancat) si i només si tots els vèrtexs tenen grau parell. - Té **camí eulerià** (no necessàriament tancat) si i només si exactament dos vèrtexs tenen grau imparell.

Exemple clàssic: ponts de Königsberg.

### 6.2 Hamiltonià

Un **cicle hamiltonià** visita tots els vèrtexs exactament una vegada.

No hi ha criteri tan simple com el d'Euler. Alguns criteris suficients: - **Dirac:** si $n\ge 3$ i $d(v)\ge n/2$ per a tot vèrtex, el graf és hamiltonià. - **Ore:** si $d(u)+d(v)\ge n$ per a qualsevol parella no adjacent, és hamiltonià.

Aplicacions: rutes (TSP), planificació, seqüenciació.

## 7. Coloració de grafs

### 7.1 Definició

Una **coloració** és assignar colors als vèrtexs de manera que vèrtexs adjacents tinguin colors diferents.

El mínim nombre de colors és el **nombre cromàtic** $\chi(G)$.

- $\chi(K_n)=n$ - Si $G$ és bipartit i té almenys una aresta, $\chi(G)=2$

### 7.2 Teorema dels quatre colors

Qualsevol mapa planar es pot pintar amb 4 colors sense que dues regions adjacents comparteixin color. Equivalent a dir que qualsevol graf planar satisfà $\chi(G)\le 4$.

## 8. Planaritat

Un graf és **planar** si es pot dibuixar al pla sense que les arestes es tallin.

- **Fórmula d'Euler (grafs planars connexos):** $$V - E + F = 2$$ on $F$ és el nombre de cares.

- Conseqüències (per $V\ge3$): $$E \le 3V-6$$ i si és bipartit planar: $$E \le 2V-4$$

- Grafs no planars típics: $K_5$ i $K_{3,3}$.

## 9. Camins més curts

En grafs ponderats, el problema de camí mínim és central.

- **Dijkstra:** pesos no negatius; calcula distàncies mínimes des d'una font. - **Bellman-Ford:** admet pesos negatius (sense cicles negatius). - **Floyd-Warshall:** distàncies mínimes entre tots els parells (programació dinàmica).

Aplicacions: GPS, xarxes, rutes de transport.

## 10. Xarxes de flux

En una xarxa dirigida amb capacitats $c(e)$, volem maximitzar el flux de $s$ a $t$.

**Teorema max-flow min-cut:** el flux màxim és igual a la capacitat mínima d'un tall $s$-$t$.

Algorismes: Ford-Fulkerson, Edmonds-Karp.

Aplicacions: trànsit, telecomunicacions, assignació de recursos.

## 11. Aplicacions didàctiques

- Treballar amb mapes del barri o de l'institut (grafs de carrers). - Problemes eulerians (recollida d'escombraries, carter). - MST per planificar una xarxa de cablejat a l'aula. - Coloració de grafs per horaris (exàmens sense solapament). - Introducció a algorismes amb pseudocodi.

## 12. Conclusions

La teoria de grafs és un marc unificador per a problemes de connexió i optimització. Concepte d'arbre, camí eulerià, MST, coloració i camí mínim apareixen en contextos reals i ofereixen excel·lents oportunitats didàctiques per treballar modelització i pensament algorísmic.