Grafo non orientato

Un grafo non orientato $G= (V, E)$ è dato da una coppia di insiemi finiti:

• $V =\{ v_1,..,v_n\}$ l’insieme degli $n$ Nodi di $G$
• $E= \{e_1,..,e_m\} \subseteq V \times V$ l’insieme degli $m$ Archi non orientati di $G$

Ogni arco non orientato $e_k = (v_i,v_j)$ di $G$ corrisponde ad una coppia non ordinata di nodi $v_i$ e $v_j$ di $G$

I nodi $v_i$ e $v_j$ sono gli estremi dell’arco $e_k$

La presenza di un arco tra una coppia di nodi indica una relazione tra i nodi stessi

Definizioni di base

• un arco $(v,v)$ è detto loop (cappio)
• un arco $e = (u,v) \in E$ si dice incidente su $u$ e su $v$
• due nodi $u,v \in V$ sono detti adiacenti $\Rightarrow (u,v) \in E$
• due archi $e_1,e_2\in E$ sono adiacenti $\Rightarrow e_1 = (u,v)$ ed $e_2 =(v,w)$ (hanno un estremo in comune)
• l’insieme di nodi $N(u) =\{v \in V:v \text{ adiacente a } u\}$ è detto intorno di $u$ in $G$
• l’insieme di archi $\delta (u) = \{e \in E: e \text{ incide su } u\}$ è detto stella di $u$ in $G$
• $|\delta(u)|$ è detto grado del nodo $u$

Grafo semplice

Non esistono “loop” o archi paralleli (ossia tra due nodi ci può essere più di un arco)

Sottografi

$G' =(V',E')$ è detto sottografo di $G=(V,E) \iff$

• $V' \subseteq V$