A blog about Front End Development, Data Science, Machine Leaning and Python.

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)

$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

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

Ti sei iscritto con successo al blog di Data Science - Machine Learning e Python
Bentornato! Hai effettuo l'accesso al blog.
Ottimo! Ti sei appena registrato.
Perfetto! Il tuo account è attivo, ed hai l'accesso a tutti i contenuti.