Els grafs són una estructura de dades fonamental en informàtica i matemàtiques, utilitzada per modelar relacions entre objectes. A diferència de les llistes, piles, cues i arbres, els grafs poden representar connexions més complexes i no necessàriament jeràrquiques.

Un graf \( G \) es defineix com un conjunt de nodes (o vèrtexs) \( V \) i un conjunt d'arestes \( E \) que connecten parelles de nodes. Formalment, un graf es representa com \( G = (V, E) \).

Els grafs es poden classificar en diverses categories segons les seves propietats:

1. Graf Dirigit (Digraf): Les arestes tenen una direcció, és a dir, van d'un node a un altre.
2. Graf No Dirigit: Les arestes no tenen direcció, és a dir, la connexió entre dos nodes és bidireccional.
3. Graf Ponderat: Les arestes tenen un pes associat, que pot representar costos, distàncies, etc.
4. Graf No Ponderat: Les arestes no tenen pes associat.
5. Graf Connex: Hi ha un camí entre qualsevol parella de nodes.
6. Graf No Connex: No hi ha camins entre algunes parelles de nodes.

• Vèrtex (Node): Un punt en el graf.
• Aresta: Una connexió entre dos vèrtexs.
• Grau d'un Vèrtex: El nombre d'arestes que incideixen en un vèrtex.
• Camí: Una seqüència de vèrtexs connectats per arestes.
• Cicle: Un camí que comença i acaba en el mateix vèrtex sense repetir arestes ni vèrtexs.

Una matriu d'adjacència és una matriu quadrada \( n \times n \) on \( n \) és el nombre de vèrtexs en el graf. L'element \( A[i][j] \) és 1 si hi ha una aresta entre el vèrtex \( i \) i el vèrtex \( j \), i 0 en cas contrari.

Exemple:

Aquest graf té arestes entre A-B i B-C.

Una llista d'adjacència és una col·lecció de llistes, una per cada vèrtex, on cada llista conté els vèrtexs adjacents al vèrtex corresponent.

Exemple:

Aquest graf té arestes entre A-B i B-C.

Aquest graf es pot representar amb una matriu d'adjacència o una llista d'adjacència.

Matriu d'Adjacència:

Llista d'Adjacència:

Matriu d'Adjacència:

Llista d'Adjacència:

Dibuixa un graf amb els següents vèrtexs i arestes, i representa'l utilitzant una matriu d'adjacència i una llista d'adjacència.

Vèrtexs: {1, 2, 3, 4} Arestes: {(1, 2), (1, 3), (2, 4), (3, 4)}

Solució:

Matriu d'Adjacència:

Llista d'Adjacència:

En aquesta secció, hem introduït els conceptes bàsics dels grafs, incloent-hi la seva definició, tipus, notació i representació. Els grafs són una eina poderosa per modelar relacions complexes i tenen aplicacions en molts camps, des de la informàtica fins a les ciències socials. En les pròximes seccions, explorarem com representar grafs en codi i com implementar algoritmes comuns per treballar amb grafs.