Definizione [Grafo non orientato]: $G = \lang V, E\rang$ dove:

• $V$ insieme finito (vertici o nodi)
• $E \subseteq V^{(2)}$ (lati)

Definizione [Grafo orientato]: $G=\lang V,E \rang$ dove:

• $V$ insieme finito (vertici o nodi)
• $E \subseteq V^2$ (archi)

Siano $G=\lang V,E \rang,n=|V|, m=|E|.$ Vale:

• $0\leq m\leq n^2$ (G orientato)
• $0 \leq m \leq \frac{n(n-1)}{2}$ (G non orientato)
• $G$ è sparso se $m = O(n)$
• $G$ è denso se $m = \Theta(n^2)$

Definizione [sottografo]: $G'=\lang V', E'\rang$ è sottografo di $G=\lang V,E \rang$ se:

• $V' \subseteq V$
• $E' \subseteq E \cap V' * V'$ (o $E' \subseteq E \cap V'^{(2)}$ se G non orientato)

Grafi: definizioni