📋 RESUM: Grafs i aplicacions
• **Graf** $G=(V,E)$: vèrtexs i arestes; pot ser dirigit o ponderat.
• **Grau** $d(v)$ i **lema de les encaixades**: $\sum d(v)=2|E|$; #graus imparells és parell.
• **Camí/cicle** i **connexió**: components connexes.
• **Representacions**: matriu d’adjacència, d’incidència i llistes d’adjacència.
• **Arbre**: graf connex sense cicles; equivalent a tenir $E=V-1$.
• **MST**: arbre d’expansió mínim; algorismes de Kruskal i Prim.
• **Euler**: circuit eulerià ⇔ tots graus parells; camí eulerià ⇔ exactament 2 graus imparells.
• **Hamilton**: visita tots els vèrtexs; criteris suficients (Dirac, Ore).
• **Coloració**: nombre cromàtic $\chi(G)$; grafs bipartits tenen $\chi=2$.
• **Planaritat**: Euler $V-E+F=2$, límits $E\le 3V-6$; no planars $K_5$, $K_{3,3}$.
• **Camins mínims**: Dijkstra, Bellman-Ford, Floyd-Warshall. **Flux**: max-flow min-cut.
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.
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à.
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.
Estudia este tema con OPOSGRATIS
Has leído el desarrollo del tema. Para consolidar tu aprendizaje, estudia las flashcards asociadas con repetición espaciada (algoritmo SM-2), realiza simulacros de examen, y practica el supuesto práctico. Todo gratis y sin registro previo.
