×
TEORIA DEI GRAFI

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
Grafo non orientato composto da 6 nodi $V$ e 7 archi $E$

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.

Grafo non orientato con la presenza di un nodo con arco verso se stesso (cappio)
Grafo non orientato con la presenza di un nodo con arco verso se stesso (cappio)

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

Grafo Multiarco
Grafo Multiarco

Un grafo multiarco è un grafo che ha nella sua struttura più archi per lo stessa coppia di nodi.

Cerca

Vuoi scrivere per noi? Guadagna scrivendo articoli per il nostro blog!