Grafi

Immagina un grafo come una rete di punti connessi tra loro da linee. I punti sono chiamati "vertici" (o nodi) e le linee che li collegano sono chiamate "archi" o "spigoli". 

• Vertici (o nodi)
  I vertici sono i punti o nodi della rete. Rappresentano gli oggetti o le entità del grafo. In genere, sono indicati con un cerchio oppure con un punto. A volte sono accompagnati anche da un'etichetta (ad esempio "A", "B", "C", ecc. ).
  

  Il numero totale di vertici è detto ordine del grafo. Ad esempio, in questo grafo ci sono cinque vertici, quindi il grafo ha ordine 5.

• Archi (o spigoli)
  Gli archi sono le relazioni tra i vertici. Puoi immaginarli come delle strade che collegano le città. Gli archi rappresentano le relazioni o le connessioni tra coppie di vertici o nodi. In genere si chiamano "spigoli" (edge, line, ecc.) quando non hanno una direzione specifica, si chiamano "archi" (arc) quando è indicato un verso di percorrenza.
  

  Il numero totale delle linee (archi o spigoli) è detto dimensione del grafo. Ad esempio, in questo grafo ci sono sette linee che collegano i vertici. Quindi il grafo ha una dimensione uguale a 7.

Un grafo viene scritto come G=(V,E) dove G rappresenta il grafo, V l'insieme dei vertici mentre è E la collezione degli archi.

$$ G = (V,E) $$

L'insieme dei vertici V contiene tutte le etichette assegnate ai vertici del grafo.

Ad esempio, l'insieme dei vertici del grafo precedente è il seguente;

$$ V = \{ A,B,C,D,E \} $$

Per indicare un arco, invece, possiamo scrivere una coppia (A,B) oppure AB, dove "A" e "B" sono gli estremi dell'arco.

Ad esempio, la collezione degli archi del grafo precedente è la seguente:

$$ V = \{ AB, AC, BC, BD, CD, CE. DE \} $$

In questo caso la collezione è composta da sette archi.

Ogni arco del grafo si collega a due vertici, che non devono necessariamente essere distinti, denominati estremi (o endpoint).

Nota che parliamo di "collezione" anziché di "insieme" perché tra due vertici di un grafo potrebbero esserci anche più linee che li collegano. In un insieme, ogni elemento deve essere unico, mentre in una collezione, possiamo avere elementi ripetuti, il che ci consente di rappresentare più connessioni tra le stesse coppie di vertici. Per rendere meglio l'idea, ecco un esempio di grafo con lati multipli tra i vertici A e B. Questi archi sono detti paralleli.

Quando due vertici sono connessi da un arco, si dice che sono "incidenti" su quell'arco, e l'arco è detto essere "incidente" ai vertici.

Ad esempio, i vertici A e B sono incidenti sull'arco AB.

Nello stesso tempo, l'arco AB è incidente sui vertici A e B.

Quando un arco parte e arriva allo stesso vertice, si parla di ciclo o loop.

Ad esempio, in questo grafo c'è un ciclo nel vertice A.

Un grafo è detto grafo semplice se non ha archi paralleli e non ha cicli.

È la versione più "pulita" di un grafo, con una sola linea (arco) diretta tra qualsiasi coppia di vertici e nessun arco che si collega a se stesso.

In caso contrario, è detto pseudografo se ha almeno un ciclo o multigrafo se ha archi paralleli ma non cicli.

Per concludere questa lunga introduzione, il grafo è detto completo quando ogni vertice è collegato a tutti gli altri vertici del grafo.

A cosa servono i grafi? I grafi vengono utilizzati per modellare relazioni tra coppie di oggetti, permettendo di rappresentare reti complesse in vari ambiti, come reti di computer, circuiti elettrici, percorsi stradali, relazioni sociali, e molto altro.

Tipi di grafi

I grafi possono essere classificati in base a diverse caratteristiche:

• Grafi orientati e non orientati
  In un grafo non orientato, gli archi non hanno una direzione specifica, indicando semplicemente che due vertici sono connessi. In un grafo orientato (o digrafo), ogni arco ha una direzione, indicando una relazione direzionale tra la coppia di vertici che unisce.
  

  

• Grafi pesati e non pesati
  In un grafo pesato, ad ogni arco è associato un peso, che può rappresentare il costo, la lunghezza, o un'altra misura della connessione tra due vertici. Nei grafi non pesati, invece, gli archi non hanno peso.
  

  

• Grafi ciclici e aciclici
  Un grafo è ciclico se contiene almeno un ciclo, ovvero un percorso chiuso che parte da un vertice e ritorna allo stesso vertice attraverso un numero finito di archi. Un grafo aciclico non contiene cicli.
• Grafi connessi e non connessi
  Un grafo è connesso se esiste un percorso tra ogni coppia di vertici. In un grafo non connesso, esistono almeno due vertici tra i quali non esiste alcun percorso.
• Grafo bipartito
  Immagina di poter dividere i vertici in due gruppi in modo che gli archi collegano solo vertici di gruppi diversi, mai vertici dello stesso gruppo. Questo grafo è detto "bipartito". Un grafo bipartito è detto completo se ogni vertice di un gruppo è connesso a ogni vertice dell'altro gruppo.
  

Queste caratteristiche permettono di utilizzare i grafi in un'ampia gamma di applicazioni, dalla ricerca dei percorsi più brevi, alla modellazione di reti di computer, alla teoria dei giochi, e oltre.

Nell'informatica teorica e applicata alcuni strumenti e algoritmi usati sui grafi sono la ricerca in profondità (DFS), la ricerca in ampiezza (BFS), l'algoritmo di Dijkstra per i percorsi più brevi, e l'algoritmo di Kruskal per la ricerca di alberi di copertura minimi

Grafi orientati e non orientati

I grafi orientati e non orientati sono due tipologie fondamentali di grafi, che differiscono per il modo in cui gli archi connettono i vertici all'interno del grafo.

Grafi non orientati

In un grafo non orientato, gli archi non hanno una direzione. Sono rappresentati da semplici linee.

Questo significa che se c'è un arco che collega due vertici \(A\) e \(B\), il vertice \(A\) è connesso al vertice \(B\) e viceversa, senza una direzione preferenziale.

In altre parole, l'arco \(AB\) è indistinguibile dall'arco \(BA\). Questi grafi sono utilizzati per modellare relazioni bidirezionali o simmetriche, dove la direzione della relazione non è rilevante o esiste un'interazione reciproca.

Esempi di applicazioni per grafi non orientati includono la modellazione di reti sociali come Facebook dove un'amicizia è mutuale, reti di computer se la comunicazione è bidirezionale, mappe stradali dove le strade permettono il traffico in entrambe le direzioni, ecc.

Nei grafi non orientati, gli archi sono rappresentati da linee semplici (senza freccia).

Grafi orientati o diretti (Digrafi)

Un grafo orientato, o digrafo, ha gli archi con una direzione specifica. Sono rappresentati da frecce che indicano il verso da un nodo all'altro.

Quindi, una caratteristica essenziale dei digrafi è la direzionalità.

In questo tipo di grafo, se un arco va dal nodo \(A\) al nodo \(B\), questo non implica che esista un arco che va da \(B\) a \(A\).

Ogni arco è quindi una coppia ordinata \((A, B)\), dove il primo elemento è il nodo di partenza e il secondo è il nodo di arrivo.

I grafi orientati sono utilizzati per rappresentare relazioni direzionali o asimmetriche. Ad esempio se inizi a seguire il canale una persona su YouTube, non significa automaticamente che quella persona si iscriverà anche al tuo canale. Un ulteriore esempio di relazioni direzionali si trova nelle reti stradali, dove ogni strada può essere caratterizzata da un senso unico di marcia o permettere la circolazione nei due sensi.

Grafi pesati

Un grafo pesato è un tipo di grafo in cui ogni arco ha un valore associato, detto peso.

Questi pesi possono rappresentare distanze, costi, tempi o qualsiasi altra misura che vuoi associare alla connessione tra due nodi nel grafo.

Per esempio, se consideri una mappa stradale come un grafo, i nodi potrebbero rappresentare le città e gli archi le strade che le collegano. Il peso di ogni arco potrebbe rappresentare la distanza tra le città, il tempo medio di percorrenza o il costo del viaggio. Ad esempio, qual è il percorso più breve per spostarsi dal nodo A al nodo D? Ci sono diversi cammini possibili ma quello a costo inferiore è quello A→B→C→D che ha un costo complessivo uguale a sei ( 3+1+2=6 ).

Gli altri cammini possibili dal nodo A al nodo D hanno un costo maggiore. Ad esempio, il cammino A→C→D costa 7, il cammino A→C→E→D costa 8, infine il cammino A→B→D costa 7.

In termini matematici, un grafo pesato può essere definito come una tripla \(G = (V, E, w)\), dove:

•  \(V\) è l'insieme dei nodi o vertici.
•  \(E\) è l'insieme degli archi o spigoli, dove un arco è una coppia di nodi che indica la loro connessione.
•  \(w: E \rightarrow \mathbb{R}\) è una funzione che assegna un peso ad ogni arco nel grafo.

Ad esempio, l'insieme dei vertici V del digrafo G precedente è

$$ V = \{ A, B, C, D, E \} $$

L'insieme degli archi E è il seguente:

$$ E = \{ AB, AC, BC, BD, CD, CE, ED \} $$

I relativi pesi degli archi sono una famiglia di coppie

$$ w = \{ (AB,3), (AC,5) , (BC,1) , (BD,4), (CD,2), (CE,1), (ED,2) \} $$

Il primo elemento di ogni coppia indica l'arco mentre il secondo elemento indica il peso associato all'arco.

Nell'analisi dei grafi pesati sono particolarmente importanti algoritmi come quello di Dijkstra, che trova il percorso più breve tra due nodi, e l'algoritmo di Prim o di Kruskal per trovare un albero di copertura minima, cioè un sottoinsieme degli archi che connette tutti i nodi con il minor costo totale possibile.