grafo

grafo

grafo [Der. del gr. grápho "scrivere"] [ALG] Configurazione (propr. g. lineare o singramma) formata da un insieme di punti, detti vertici o nodi del g., e di linee, dette lati o spigoli del g., che uniscono coppie di vertici. La teoria di tali configurazioni (teoria dei g.) ha preso storicamente lo spunto nei primi decenni del 18° sec. da elementari problemi topologici, come il celebre problema dei sette ponti di Königsberg (←), o quello che chiede se sia possibile collegare ciascuna delle tre case C₁, C₂, C₃ (fig. 1) a ciascuno dei tre pozzi P₁, P₂, P₃ con sentieri che non si intersechino (la risposta è negativa: v. oltre). Una prima classificazione distingue i g. finiti, che cioè hanno un numero finito di vertici e di spigoli, dai g. infiniti (sono spec. i g. finiti che interessano le applicazioni); si hanno poi i g. completi, nei quali due qualsiasi vertici sono congiunti da un lato (fig. 2), e i g. incompleti, nei quali ciò non accade. Nella fig. 3 sono indicati un g. incompleto e il suo g. complementare, che è costituito dagli spigoli che occorre aggiungere al g. dato per renderlo completo. Particolari g. incompleti sono gli alberi : in essi non esiste nessun cammino chiuso costituito da lati del g. e, di conseguenza, due vertici qualsiasi sono congiunti da un unico cammino. Di un g. si può sempre costruire un'immagine nell'ordinario spazio a 3 dimensioni mediante punti e segmenti di retta, in modo che due qualunque spigoli non abbiano nessun punto in comune, salvo il caso che escano da uno stesso vertice. Naturalmente può accadere che un g. sia addirittura planare (o piano), cioè si possa rappresentare su un piano in modo da soddisfare alla condizione ora indicata; di norma, peraltro, un g. non è planare, neanche se si ammette (come del resto si fa sempre) che gli spigoli possano essere linee curve anziché segmenti di retta. Sono, per es., non planari i g. delle figg. 1 e 2.4. Al riguardo, un teorema di Kuratowski afferma che un g. è planare se e soltanto se non contiene come sottografo nessuno dei due g. delle figg. 1, 2.4 (si ottiene un sottografo di un dato g. quando di esso si considerano solo alcuni vertici e alcuni spigoli). Un ordinario poliedro convesso con i suoi vertici e spigoli, costituisce, nonostante possa sembrare il contrario, un g. planare (per convincersene basta proiettare i suoi vertici e i suoi spigoli da un punto interno al poliedro sopra una superficie sferica racchiudente il poliedro medesimo; si ottiene così un g. tracciato sulla sfera; se ora si proietta stereograficamente la sfera su un piano, si ottiene appunto un g. piano: nella fig. 4 sono rappresentati i g., piani di un prisma esagonale e dei cinque poliedri regolari). I g. non planari si possono classificare sulla base di un numero intero, il cosiddetto genere del g.: un g. si dice di genere p>1 quando si può rappresentare su una ciambella a p buchi senza che due spigoli si incontrino in punti che non siano vertici. Il g. completo con 5 vertici è di genere 1, dato che si può rappresentare su una ciambella con un solo buco, ossia su un ordinario toro (fig. 5). Il classico problema dei ponti di Königsberg si può porre per un g. qualsiasi: ci si può chiedere se un g. si può percorrere interamente senza interruzioni e senza passare più di una volta su uno stesso spigolo, ossia se esso è, come si suol dire, un g. di Eulero. Ebbene, un g. è di Eulero se ogni suo vertice è pari, ossia se da ogni vertice esce un numero pari di spigoli oppure se vi sono due soli vertici dispari (e in questo caso il percorso deve avere inizio da uno di questi due vertici e terminare nell'altro). Nella fig. 6 sono rappresentati due g. di Eulero, con l'indicazione di un percorso del tipo indicato, e un g. che non è un g. di Eulero. Meno semplice è invece stabilire se e in qual modo è possibile percorrere gli spigoli di un g. in modo da passare una e una sola volta per ciascun vertice. Un percorso di tale tipo si chiama linea di Hamilton del g., e non si conosce tuttora un criterio generale per distinguere i g. che possiedono tali linee da quelli che ne sono privi. Nella fig. 7 è rappresentata una linea di Hamilton per il g. costituito dai vertici e dagli spigoli di un ottaedro regolare. In alcuni problemi della teoria dei g. è utile la nozione di isomorfismo tra g.: due g. si dicono isomorfi quando hanno lo stesso numero di vertici e inoltre si può stabilire tra i vertici del primo e quelli del secondo una corrispondenza tale che due vertici del primo congiunti da uno spigolo abbiano come immagini due vertici del secondo congiunti da uno spigolo, e viceversa. Sono tali i g. della fig. 8. Ricorderemo infine che talvolta è opportuno assegnare un verso a ciascuno spigolo del g., e allora si parla di g. orientato, oppure a qualche spigolo soltanto ottenendo così un g. misto. Il g. misto della fig. 9 raffigura schematicamente una rete di strade di una città, con l'indicazione dei tratti a senso unico. ◆ [FTC] La teoria dei g. ha trovato recentemente largo impiego come strumento di analisi in vari campi delle scienze applicate, quali la chimica, la meccanica statistica, l'organizzazione e la programmazione industriale, la teoria economica dei trasporti, i controlli automatici, ecc. Nei casi più semplici l'uso dei g. serve a schematizzare il flusso di segnali, di informazioni, di quantità, ecc., oppure l'insieme di relazioni sequenziali che legano tra loro varie attività, vari organi, ecc. In partic., nella teoria dei controlli automatici, i g. servono per una visualizzazione dell'insieme di equazioni simultanee che descrivono un sistema; la trasmissione dei segnali è rappresentata graficamente in modo analogo a quanto si fa con i diagrammi a blocchi, ai quali si preferiscono spesso i g. perché più facili a disegnarsi e soprattutto perché più facili a essere manipolati per la risoluzione di particolari problemi. I g. impiegati (chiamati comunem. g. di flusso) sono sempre del tipo orientato e il verso indica la direzione del flusso del segnale: i nodi rappresentano le variabili, mentre i lati che li uniscono rappresentano le funzioni di trasferimento. Alcuni elementi del g. sono partic. significativi; per es.: i nodi di ingresso, o sorgenti, rappresentativi delle grandezze di ingresso e dai quali "escono" alcuni lati mentre non ne "arriva" nessuno; i nodi di uscita, rappresentativi delle grandezze di uscita e nei quali "arrivano" lati e non ne "esce" nessuno; le maglie chiuse, o di controreazione, individuate dalla successione di lati che si possono percorrere nel senso delle frecce partendo da un nodo e facendovi ritorno (tali maglie individuano le controreazioni del sistema). L'impiego dei g. si rivela partic. utile in sistemi molto complessi, dove le funzioni di trasferimento sono in generale funzioni del tempo o della frequenza o di altre quantità. Le relazioni che legano le variabili del sistema hanno un'immediata corrispondenza in un g., che può essere successiv. trasformato in g. più semplici (con numeri inferiori di nodi e di lati) e più adatti a studi di stabilità o a considerazioni sui disturbi nel sistema. Nella fig. 10 sono riportati una rete elettrica, per la quale valgono le relazioni I₁=(1/R₁)V₁-(1/R₁)V₂, V₂=R₃I₁-R₃I₁, I₂=(1/R₂) V₂-(1/R₂)V₃, V₃=R₄I₂, e il corrispondente g., ottenuto scegliendo come grandezza d'ingresso la tensione V₁ di alimentazione e come grandezza d'uscita la tensione V₃.