Che cos'è la teoria dei grafi e come si definisce un grafo come tale?

Nel 1736, sulla base dell'opera del fisico-matematico svizzero Leonhard Euler (1707-1783), si osservò che una successione di vertici definisce un percorso, invece, se detto percorso è costituito da vertici diversi senza archi ripetuti, è chiamato percorso o percorso euleriano; se inoltre arriviamo al punto di partenza, attraversando ogni spigolo una sola volta, allora abbiamo un ciclo euleriano (circuito).

Preventivo (APA)

Alessandro Barraza | lug. 2022
Laurea in fisica

Da parte sua, definiamo un grafico come una coppia ordinata (VA) dove v designa l'insieme (non vuoto) di tutti i vertici o nodi di un grafo, mentre UN designa l'insieme (può essere vuoto) di tutti gli spigoli o linee che uniscono i vertici di un grafo. Gli elementi dell'insieme UN può essere designato come una coppia non ordinata {v, w} dove v e w sono elementi (nodi o vertici) di v, in questo modo si dice allora che v e w sono vertici adiacenti (sono uniti da uno spigolo).

La teoria dei grafi nasce dalla risposta data da Eulero a un problema di ingegno popolare che si chiedeva come attraversare i sette ponti che si unì a due isole della comunità di Königsberg (allora parte della Germania, e attualmente Kaliningrad, in Russia), tra loro e con la terraferma senza utilizzare due volte lo stesso ponte e arrivando al punto di partenza (situato sulla terraferma) qualunque esso sia, determinando che in questo caso, in definitiva, non Potevo.

Il problema dei sette ponti di Königsberg

Eulero ha modellato Königsberg come un grafico in cui ogni punto (vertice o nodo) rappresenta un ponte e ogni linea (bordo) un percorso sulla terra:

Qual è la soluzione a questo problema?

non ce n'è uno soluzione che soddisfa le condizioni imposte, poiché, come mostrò Eulero, i vertici non sono di grado pari, cioè un numero pari di rette non interessa ogni punto _[3]. Non sembra che si possa fare molto con una struttura definita semplicemente così, tuttavia, come spesso accade matematica, A volte le cose non sono come sembrano. Quindi, uno degli ambiti più prolifici, trasversali e interdisciplinari _[4] della conoscenza umana, teoria dei grafi.

Grafici euleriani o con traiettoria euleriana?

I seguenti grafici hanno tutti percorsi euleriani _[5]. Hanno tutti i cicli euleriani?

Prendiamo il terzo grafico:

Numeriamo i vertici:

Vediamo allora che il cammino definito dalla successione {3,4,6,2,1,3,7,6,5,4,2} è un cammino euleriano, poiché percorre l'intero grafo senza ripetere gli archi, ma non è un ciclo euleriano, poiché non raggiunge il punto di partenza. Cosa sarebbe successo se avessimo numerato i vertici in modo diverso? Non molto, tranne che ora il percorso sarebbe definito da una successione diversa. Cosa sarebbe successo se avessimo seguito strade diverse da quella proposta nella nostra soluzione iniziale? Questa domanda è un po' più complessa a cui rispondere e coinvolge algoritmi di cui gli ingegneri del software di solito sono entusiasti. programmazione.

Per una dimostrazione più rigorosa di quanto qui esposto dobbiamo fare riferimento al seguente risultato:

"Essere G un grafico connesso _[6]. Allora si G avere un circuito Eulero, il grado di ogni vertice è pari, mentre se G ha un cammino di Eulero, G ha esattamente due vertici di grado dispari _[7] (esattamente i vertici dove inizia e finisce il percorso)".

Possiamo quindi verificare che, infatti, nel grafo che prendiamo, solo i vertici 3 e 6 hanno grado dispari (questo si verificherebbe anche se la numerazione dei vertici fosse stata diversa), quindi detto grafo ha un percorso euleriano _[8]. Per i restanti grafici possiamo procedere in modo analogo e verificare se effettivamente hanno cammini e Cicli euleriani, o in altre parole, possiamo disegnare tali grafici senza prendere la matita e ripetere linee? La risposta a questa domanda può essere dedotta da quanto già spiegato finora, ma costituisce un esercizio interessante in termini di motricità fine, ingegno e pazienza, invito il lettore a trovare e disegnare grafici di 6 o più vertici con traiettoria Euleriano.

Ci sono altri tipi di grafici? La teoria dei grafi ha applicazioni nel mondo "reale"?

Questi grafici che abbiamo esaminato molto brevemente, sono solo uno dei tanti tipi di grafici che troviamo nella teoria dei grafi. Possiamo anche trovare grafici come alberi, molto rappresentativi negli insiemi dove i loro elementi possono essere classificati in gerarchie e nei calcoli di conteggio e probabilità_[9], digrafi, grafi hamiltoniani _[10], eccetera.

Immagine di modelli grafici e reti in Psycho., di Ruiz, Ana María.

Questi enigmi, se così vogliamo chiamarli, hanno enorme applicabilità nel mondo di oggi, in situazioni tanto diverse come: biologia molecolare _[11], informatica_[12], telecomunicazioni _[13] e analisi di rete _[14]. Vale la pena chiedersi allora: non è almeno curioso che sia un problema di quasi banale finirà per essere uno dei risultati più interessanti e cospicui della matematica? Forse, per questo, era necessario il contributo di una delle menti più illustri dell'umanità.