Con "Grafi" intendiamo una struttura matematica discreta. Ad esempio possiamo immaginare i "punti" di un grafo come se fossero delle persone e le "linee" che li connettono le loro relazioni d'amicizia.
Partendo da questo sunto di base possiamo dire che la Teoria dei grafi si occupa di definire strutture di svariati tipi, come ad esempio gli ipertesti, i social network e una moltitudine di situazioni e processi.
I grafi sono costituiti da:
- Nodi (o vertici) $V$ che sono i punti citati precedenza
- Archi (o connessioni) $E$ che sono le linee che connettono i nodi
Un grafo $G$ è una tripla ordinata di $(V(G), E(G) psi G)$ consistente di un set vuoto $V(G)$ di vertici e un set $E(G)$, disgiunto da $V(G)$, di archi, ed una funzione d'incidenza $psi G$ che associa ad ogni arco di $G$ una coppia non ordinata (non necessariamente distinta) di vertici di $G$.
Prendendo in esempio l'immagine precedente avremo che:
$$G = {V(G), E(G) psi G}$$
dove $V(G) = {psi_{1}, psi_{2}, psi_{3}, psi_{4}, psi_{5}}$
e $E(G) = {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}, e_{6}, e_{7}}$
e $psi$ è definita
$$psi_{g} (e_{1}) = v_{a} v_{f},$$ $$psi_{g} (e_{2}) = v_{f} v_{e},$$ $$psi_{g} (e_{3}) = v_{a} v_{e},$$ $$psi_{g} (e_{4}) = v_{a} v_{b},$$ $$psi_{g} (e_{5}) = v_{b} v_{e},$$ $$psi_{g} (e_{6}) = v_{b} v_{c},$$ $$psi_{g} (e_{7}) = v_{c} v_{d}$$
Vengono chiamati "Grafi", poiché li possiamo rappresentare graficamente, la loro rappresentazione ci aiuta molto nel capire le loro proprietà.
Ciascun nodo è indicato da un punto e ciascun arco da una linea che connette i punti.
Non c'è un modo unico per rappresentare i grafi!
Se $e = {i, j}$ è un arco, chiameremo $e = i, j$ la fine di $e$, e diremo che $e$ è incidente in $i$ e $j$. Due nodi $i$ e $j$ sono detti adiacenti, o vicini, se ${i, j}$ è un arco.
$G = (V, E), V = {a, b, c, d},$
$E = {(a, b), (a, c), (d, d)}$
Il vicino di un nodo $i$, è il sottoinsieme $N_{G}(i) = {j in V : i j in E}$.
Un grafo $G$ è detto finito se entrambi $V$ e $E$ sono sottoinsiemi finiti.
Un grafo multiarco è un grafo che ha nella sua struttura più archi per lo stessa coppia di nodi.
