Grafi

Un grafo $G=(V,E)$ ha cardinalità $n=|V|$ e $m=|E|$.

Viene definito orientato se le coppie $(v_1,v_2)\in E\subseteq V\times V$ sono ordinate, da cui: $$|V\times V|=|V^2|=|V{|}^2$$

Per esempio, se $V=\{1,2,3\}$ e $E=\{(1,3),(2,1),(2,2),(3,1),(3,2)\}$:

Viene detto non orientato (n.o.), se soddisfa le proprietà di:

• Simmetria, se $\forall (v,u)\in E,(u,v)\in E$
• Non riflessività, se $\forall v\in V,(v,v)\notin E$ per cui non sono ammessi cappi

In alternativa è definito n.o. se $E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$, cioè l'insieme dei sottoinsiemi di $V$ formati da due elementi: $$\left|\left(\genfrac{}{}{0ex}{}{V}{2}\right)\right|=\left(\genfrac{}{}{0ex}{}{|V|}{2}\right)=\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$$

Per esempio, se $V=\{1,2,3\}$ e $E=\{\{1,3\},\{2,3\}\}$: