Grafi non direzionati

$G = (V,E)$

• $V$ insieme di nodi
• $E$ insieme di archi
• esprime le relazioni tra coppie di oggetti
• parametri del grafo:
  • $n = |V|$
  • $m = |E|$

Grafi direzionati

Gli archi hanno una direzione

• l’arco $(u,v)$ è diverso dall’arco $(v,u)$
• si dice che l’arco $e=(u,v)$
  • lascia $u$ ed entra in $v$
  • $u$ è l’origine dell’arco e $v$ la destinazione dell’arco

Grafi non direzionati $G=(V,E)$ possono essere visti come un caso particolare di grafi direzionati in cui per ogni arco $(u,v)$ c’è l’arco di direzione opposta $(v,u)$

Terminologia

Consideriamo due nodi $u$ e $v$ di un grafo $G$ connessi dall’arco $e = (u,v)$

Si dice che:

• $u$ e $v$ sono adiacenti
• $u$ e $v$ sono le estremità dell’arco $(u,v)$
• l’arco $(u,v)$ incide sui vertici $u$ e $v$
• $u$ è un nodo vicino di $v$
• $v$ è un nodo vicino di $u$

Dato un vertice $u$ di un grafo $G$: