Teoria dei grafi applicata al mondo reale

La teoria dei grafi, con i suoi algoritmi e le sue proprietà matematiche sviscerate in lungo e in largo, è una delle prove più lampanti del fatto che la teoria non sia “solo teoria”, come l’approccio pragmatico tende spesso a declassarlo: dietro la teoria c’è la potenza della scoperta e quella delle parole, e non solo chiacchiere da universitari. Più che altro la teoria andrebbe nobilitata di per sè, ma è un lungo percorso culturale da intraprendere e non è il caso di approfondirlo qui: ci interessa proporre un po’ di teoria dei grafi e far vedere soprattutto come si possa applicare al mondo reale.

Definizione grafo

Guadagna criptovalute con il programma fedeltà di Youhodler

---

Un grafo (indicato con la lettera G) è una struttura afferente alla matematica discreta, cioè quella costituita da numeri interi, che è composto generalmente da due insieme N e A:

G = (N, A)

N indica i Nodi del grafo mentre A indica gli archi, con notazione inglese edges e nodes, mentre in alcuni vecchi libri di teoria i nodi possono essere indicati come vertici. Un grafo è rappresentabile come una coppia di insiemi N ed A, dove N è dato da una serie di etichette univoche (lettere o numeri senza ripetizioni), che rappresentazion le varie “zone” del grafo, mentre A è composto dalle coppie di nodi che sono effettivamente raggiungibili.

Grafo non orientato e grafo completo

Per intenderci, il seguente grafo presenta N e A fatti come indicato:

N = {1, 2, 3, 4, 5, 6}

A = {(1,2), (1,5), (5,2), (5,4), (4,3), (3,2), (6,4)}

e si tratta di un grafo non orientato, dato che non è indicato il verso di percorrenza dello stesso. A è composto da un sottoinsieme di tutte le possibili combinazioni di coppie di nodi, che sono numericamente pari al prodotto cartesiano N x N, tutte le combinazioni possibili escludendo le non-coppie come (3,3), di cardinalità:

n * (n-1) / 2 = 6 * 5 / 2 = 15  // numero massimo di archi con n nodi a disposizione

ovvero enumerando le possibili coppie di n nodi (numero di archi) senza ripetizione (dette combinazioni, tecnicamente) avremmo:

(1, 2), (1, 3), (1, 4), (1, 5), (1, 6),
(2, 3), (2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6),
(4, 5), (4, 6),
(5, 6)

Quindi, in un grafo totalmente connesso con 6 nodi, ci sono 15 archi. Il grafo in questo caso sarà completo.

I grafi sono dotati di proprietà matematiche di vario genere, abbastanza complesse da mettere nero su bianco in modo divulgativo, e rappresentano un modello per molte cose del mondo reale: reti di calcolatori, connettività di router, relazioni tra persone, reti sociali, strade e via dicendo.

L’interno di un grafo si possono definire vari aspetti ulteriori:

1. Per esempio posso inserire delle etichette sui nodi, che rappresentano una quantità di materiale che posso spostare da una parte all’altra, perché pone il grafo come utile per stabilire le consegne e le tempistiche delle app di logistica (e anche di quelle di Glovo, in parte).
2. Posso anche inserire dei “pesi” sugli archi per indicare i tempi di percorrenza oppure la lunghezza di una strada, in modo tale che poi possa minimizzare il cammino che è necessario percorrere, ad esempio, per andare da un punto A fino a un punto B diverso da A.
3. Posso creare dei grafi che presentano dei cicli, ovvero della sequenza in cui il primo e l’ultimo nodo è stesso, che è il caso pratico in cui un fattorino lavora su una rete di consegne e alla fine deve riportare il furgone al magazzino.
4. Posso inoltre definire dei grafi in cui non siano presenti dei cicli (detti alberi), il che mi aiuterà a definire delle strutture gerarchiche, possono aiutarmi a implementare processi decisionali di vario genere, oppure app di intelligenza artificiale. A loro volta, gli alberi possono essere binari se hanno massimo due nodi in uscita da ogni nodi, n-ari se ne hanno n, gli alberi binari vengono utilizzati per rappresentare in modo efficiente gli indici dei database.

Non finisce qui perché si possono fare molte altre cose: definire per esempio il grado di un nodo, ovvero il numero di archi che escono dallo stesso, definire dei grafi in cui sia possibile avere dei collegamenti tra un nodo e se stesso (alcune applicazioni potrebbero dare senso ad una cosa del genere), in genere l’argomento è talmente vasto che esistono numerosi libri per coprire argomento, e molto spesso neanche bastano. Quello che ci interessa se il grado di ogni nodo e pari si tratta di un grafo euleriano, che gode di determinate proprietà e “raccomandazioni”: ad esempio la possibilità di eseguire al suo interno algoritmi specialistici più efficenti della media.

Sono su queste strutture sono consolidati da anni, e sono già presenti e pronti all’uso all’interno dei linguaggi di programmazione.  Grafi e alberi vengono in genere rappresentati, per concludere, o come liste di oggetti oppure come matrici di numeri.

Algoritmo BFS (Breadth-First Search)

Altre applicazioni nel mondo reale

Gran parte della matematica che viene usata nei grafici viene assunta come implicita, E in larga parte oggetto di studio da parte dei matematici più specializzati in genere bisognerebbe quasi sempre aspettarsi che possano esistere, un giorno, dei miglioramenti agli algoritmi esistenti. La cosa incredibile di questo genere di applicazioni e che viene utilizzata ogni giorno, spesso senza che neanche ce ne accorgiamo – E ci sono applicazioni sui grafici che possono supportare per esempio le decisioni che prendiamo ogni giorno, pure che fanno uso di graffi particolari che sono detti alberi, in cui non sono presenti cicli, e che si chiamano alberi decisionali.

Non è difficile immaginare il concetto di cammino all’interno di un grafo, a questo punto: la ricerca dei cammini è una delle cose che sono state più studiate storicamente all’interno di questa disciplina. Molti problemi sono stati risolti da tempo e molti altri sono noti soltanto a livello teorico, o meglio: esistono degli algoritmi approssimati ho visti per risolverli, ma non c’è un metodo per farlo che sia esatto (cioè che produca un risultato completamente corretto). Le approssimazioni sono, nostro malgrado, l’unica strada percorribile in molti casi, dato che la complessità temporale-spaziale di questi problemi è in genere molto elevate. Ma le applicazioni?

Google Maps

Proviamo a pensare per un attimo a Google Maps, che molti di noi utilizzano abitualmente come navigatore: se vogliamo andare da casa nostra fino al cinema, ad esempio, ci propone diverse alternative che si basano sul fatto di essere a piedi, di avere una macchina, di voler prendere i mezzi pubblici e così via.

Per determinare il percorso vengono effettuati dei calcoli appositi su un grafo modellato sulla rete stradale, dove bisognerà fare qualche approssimazione per definire la “percorribilità” dello stesso e dove, per intenderci, i nodi sono dislocati in vari punti della strada, per cui se ci troviamo ad es. in un’area di 10 m² è plausibile che ci siano più nodi, dipende da come sono stati implementati e dalla convenienza nel farlo. Se poi ci sono degli edifici o degli ostacoli, pure se ci sono delle strade percorribili a piedi e non con la macchina, mira a creare più grafi per ogni possibile percorso. Nota a margine per completezza: su una rete stradale tipicamente il grafo sarà orientato, dato che esistono i sensi unici – e in generale non è possibile percorrere tutte le strade in qualunque verso.

Per semplificare il discorso in termini comprensibili, possiamo provare a immaginare un percorso che ci porti da casa al cinema (e viceversa) con la possibilità di risparmiare benzina, oppure di arrivare nel minor tempo possibile. A seconda dell’obiettivo che abbiamo cambieranno le strategie, e saranno possibili diverse varianti tutte di pari interesse, al variare del contesto.

Cammino più breve

  A --- B
   | \   | \
   |   \ |   \
   C --- D --- E
         \   /
          \ /
           F

👇 Da non perdere 👇

• 📈 Analizza Cellulari 📱
• 🔐 AI che dolor, Chat 🏴
• 🎯 Targetizza Database SQL 🗄
• 📊 Analizza Errori più comuni 📛
• 🚧 Costruisci Evergreen 📟
• 👩‍💻 Programma Gratis 🎉
• 💻 Configura Hosting a confronto 💑
• 🔒 Conosci Hosting reti e domini 💻
• 👩‍💻 Tapioca Informatica 🖥
• 💻 Iconizza Internet 💻
• 🔒 Gestisci Lavoro 🔧
• 💡 Mostra Marketing & SEO 🌪
• 🔑 Apprendi Meteo ⛅
• 🤯 Visiona Mondo Apple 🍎
• 🔍 Supervisiona Mondo Domini 🌐
• 🚀 Metti in cloud monitoraggio servizi online 📈
• 🔮 Anatomizza Nuove tecnologie 🖥
• 🔒 Antani PEC e firma digitale 📩
• 👀 Prematura Programmare 🖥
• 🎮 Lonfa Scrivere 🖋
• 🔒 Conosci Servizi di SMS 📶
• 👀 Guarda Sicurezza informatica e privacy digitale 🖥
• 🎮 Ricorda Siti web 🌎
• 🤖 Ottimizza Spiegoni artificiali 🎓
• 🧠 Neuralizza Svago 🎈
• 📡 Quantizza Usare Excel 🌀
• 🤖 Sovrascrivi Windows 😲
• 🎨 Personalizza Wireless 🚁
• 🔑 Decifra WordPress 🤵
• 💬 Il nostro canale Telegram: iscriviti
• 🔴 Che cos’è una mistificazione
• 🔴 Servizi di hosting per blog: guida alla scelta
• 🔴 Errore 403 su DAZN spiegato ai comuni mortali (e qualche indizio per risolvere)