I grafi sono “dappertutto”

Servono a rappresentare delle informazioni, di qualsiasi tipo:

• strade
• persone di un social network
• ….

Grafo orientati

E’ una relazione E : V ←→ V su un’insieme finito V.

Con V si indicano i nodi o vertici mentre con E si indicano gli archi o lati.

|V| {0,1,2,3,4,5} = 6 *nodi |*E| {(0,0) (0,1) (0,5) (1,3) (1,5) (2,1) (3,2) (3,4) (3,5) (5,3) (5,4)} = 9 archi

<aside> 💡 Un’arco (0,0) è chiamato cappio.

</aside>

Vicinato di uscita e Grado dei nodi

I nodi sono adiacenti solo sè x, y appartengono ad E o y, x appartiene ad E

• Vicinato in uscita: le frecce che dall’elemento puntano verso altri

• Vicinato in ingresso: sono le frecce che arrivano all’elemento

• Grado d’uscita: indica il numero di frecce in uscita