Grafi

1.1 Definizione di grafo e i suoi componenti

Grafo — è una struttura dati composta da un insieme di nodi (o vertici) e da un insieme di archi (o archi diretti), che connettono questi nodi. I grafi sono ampiamente usati per modellare e rappresentare vari oggetti e le loro interrelazioni.

Componenti principali del grafo:

Vertici:

• Elementi del grafo che rappresentano oggetti.
• Indicati come V (insieme dei vertici).
• Per esempio, V = {A, B, C, D}.

Archi:

• Connessioni tra vertici che rappresentano relazioni.
• Indicate come E (insieme degli archi).
• Per esempio, E = {(A, B), (B, C), (C, D), (A, D)}.

Caratteristiche principali del grafo:

Grado di un vertice:

• Il numero di archi incidenti su un dato vertice.
• In un grafo non orientato, il grado di un vertice è il numero di archi che collegano quel vertice ad altri.
• In un grafo orientato, si distinguono il grado entrante e uscente di un vertice.

Percorso in un grafo:

• Sequenza di archi che connette una sequenza di vertici.
• Per esempio, un percorso da A a D: A → B → C → D.

Ciclo in un grafo:

• Percorso che inizia e termina nello stesso vertice.
• Per esempio, un ciclo: A → B → C → A.

1.2 Tipi di grafi

I grafi possono essere di diversi tipi, tra cui alcuni particolarmente interessanti:

1. Grafo non orientato:

Gli archi di questo grafo non hanno direzione, cioè la connessione tra due vertici può essere percorsa in entrambe le direzioni.

Esempio:

Social network, dove i nodi rappresentano persone e gli archi rappresentano le loro amicizie.

2. Grafo orientato:

Gli archi del grafo hanno direzione (e solitamente sono indicati con frecce), cioè la connessione tra due vertici può essere percorsa solo in una direzione.

Esempio:

Grafo di link su pagine web, dove i nodi sono pagine e gli archi sono link tra di esse.

3. Grafo pesato:

Gli archi hanno pesi (numeri), che possono rappresentare distanze, costi o altre misure.

Esempio:

Grafo delle strade, dove i nodi sono città e gli archi sono strade con la loro lunghezza o costo di percorrenza.

4. Grafo misto:

Contiene sia archi orientati che non orientati.

Esempio:

Sistemi di trasporto, dove alcune strade sono a doppio senso e altre a senso unico.

5. Grafo planare:

Un grafo che può essere disegnato su un piano in modo che i suoi archi non si incrocino.

Esempio:

Grafo delle strade in una città (senza tunnel).

6. Grafo connesso:

Grafo in cui esiste un percorso tra ogni coppia di vertici.

Esempio:

Grafo che rappresenta una rete di città, dove ogni coppia di città è connessa da una strada.

7. Grafo aciclico:

Grafo che non contiene cicli.

Esempio:

Albero che rappresenta la struttura del file system.

1.3 Esempi di applicazione dei grafi

1. Social network:

• I nodi rappresentano persone e gli archi le amicizie tra di loro.
• Utilizzato per analizzare connessioni, trovare comunità, influenza degli utenti e così via.

2. Internet e routing:

• I nodi rappresentano router o computer e gli archi le connessioni tra di essi.
• Utilizzato per trovare percorsi ottimali per la trasmissione dei dati.

3. Genomica:

• I nodi rappresentano geni o proteine e gli archi le interazioni tra di essi.
• Utilizzato per analizzare dati genomici, trovare pattern e così via.

4. Logistica e trasporto:

• I nodi rappresentano città o nodi di trasporto e gli archi strade o percorsi.
• Utilizzato per ottimizzare i percorsi di consegna, minimizzare i costi e così via.

5. Reti di computer:

• I nodi rappresentano dispositivi o server e gli archi le connessioni tra di essi.
• Utilizzato per progettare e gestire reti.

6. Analisi dei dati e machine learning:

I grafi sono utilizzati per rappresentare e analizzare dati, trovare cluster, creare sistemi di raccomandazione e così via.