Grafs. Aplicacions

📋 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.