Grafi e retiIntroduzione

Ogni giorno siamo circondati da innumerevoli connessioni e reti: strade e binari, linee telefoniche, Internet, circuiti elettronici e persino legami molecolari. Esistono anche social network per mantenere i contatti tra amici e famiglie. Riesci a pensare ad altri esempi?

Reti stradali e ferroviarie

Computer chip

Catene di approvvigionamento

Amicizie

Connessioni neurali

Internet

In matematica, tutti questi esempi possono essere rappresentati come grafi

(da non confondere con i grafici di una funzione). Un grafo è costituito da alcuni punti chiamati ???, alcuni dei quali sono collegati da ???.

La Teoria dei grafi è lo studio dei grafi e delle loro proprietà. È una delle aree più interessanti e visive della matematica e ha innumerevoli applicazioni importanti.

Possiamo disegnare il layout di semplici grafi usando cerchi e linee. La posizione dei vertici e la lunghezza dei bordi è irrilevante - ci preoccupiamo solo di come sono collegati l'uno all'altro. I bordi possono anche incrociarsi e non è necessario che siano dritti.

In alcuni grafi, i bordi vanno solo in una direzione. Questi sono chiamati grafici diretti o orientati

Alcuni grafi sono costituiti da più gruppi di vertici che non sono collegati tra loro da bordi. Questi grafici sono indiretti o non orientati.

Altri grafi possono contenere più spigoli tra le stesse coppie di vertici o vertici collegati a se stessi (anelli).

Siamo in grado di creare nuovi grafi da un grafo esistente rimuovendo alcuni vertici e bordi. Il risultato si chiama sottografo

. Qui puoi vedere alcuni altri esempi di grafi, con bordi e vertici colorati che indicano un possibile sottografo:

Diciamo che l'ordine

di un grafo è il numero di vertici. Il grado di un vertice è il numero di spigoli che si incontrano in quel vertice.

Ordine:

Laurea:

I grafi costituiti da un singolo ciclo di vertici sono chiamati cicli

. Tutti i cicli hanno ???.

Dopo aver visto tutte queste nuove definizioni, esploriamo alcune delle affascinanti proprietà e applicazioni dei grafi.