Introduzione Grafi

Grafo

Grafo definito da $G(V,E)$, dove:

• $V$ è l’insieme dei vertici
• $E$ è l’insieme degli archi

E definiamo $n=|V|$ e $m=|E|$.

Grado di un nodo

Il grado di un nodo è il numero di archi di cui fa parte.

Se il grafo è diretto allora esiste anche il grado entrante ed il grado uscente:

• Grado entrante: numero di archi …
• Grado uscente: numero di archi …

Tipi di Grafi

Grafo Diretto

Un grafo si dice diretto quando i gli archi hanno una direzione.

$$\begin{array}{rl}& -0\le m\le n(n-1)=O(n^2)\text{se il grafo eˋ diretto}\\ & -0\le m\le \frac{n(n-1)}{2}=O(n^2)\text{se il grafo non eˋ diretto}\end{array}$$

---

Un pozzo è un nodo senza archi uscenti, un pozzo si dice universale se tutti gli altri nodi del grafo hanno un arco uscente verso il pozzo, esiste un solo pozzo universale.

Una sorgente è un nodo con soli archi uscenti.

Grafo Sparso o Denso

Un grafo si dice sparso se $m=O(n)$.

Un grafo si dice denso se $m=\Omega (n^2)$.

oss: esistono grafi che non sono ne densi ne sparsi, es. $m=\Theta (n\log n)$.

Grafo Completo

Un grafo si dice completo se se ha tutto gli archi possibili, ovvero $m=\Theta (n^2)$.

Grafo Connesso

Un grafo connesso è un grafo in cui esiste un percorso tra ogni coppia di vertici. In altre parole, è possibile raggiungere ogni vertice da ogni altro vertice attraverso una sequenza di archi.

Torneo

Un grafo si si dice torneo se tra ogni coppia di nodi c’è esattamente un arco, ovvero $m=\Theta (n^2)$.

Grafo Planare

Un grafo si dice planare se è possibile disegnarlo sul piano senza che gli archi si intersechino.

Teorema di Eulero

Un grafo planare di $n>2$ nodi ha al più $3n-6$ archi

• La prima colonna della tabella ci mostra il numero m di archi di un grafo completo di n nodi, ovvero il numero m massimo di archi.
• La seconda colonna ci mostra il numero m di archi fino a cui un grafo di n nodi ha la possibilità di essere planare.

Quindi ad esempio un grafo da 6 nodi e 13 archi è sicuramente non planare, ma con 12 archi potrebbe essere planare.

Albero

Un albero è un grafo sparso connesso senza cicli.

Info

• I nodi di grado 1 in un albero vengono chiamati foglie.
• In un albero di n nodi ci saranno esattamente m = n-1 archi (per questo un albero è sempre sparso).
• Se rimuoviamo una foglia rimane comunque un albero.
• Tutti li alberi sono grafi planari, ma non tutti i grafi planari sono alberi.