grafo

grafo

s. m. [dal tema del gr. γράϕω «scrivere»]. – In matematica, configurazione (detta più propriam. g. lineare o singramma) formata da un insieme di punti (vertici o nodi del g.) e di linee (lati o spigoli del g.) che uniscono coppie di vertici, la cui utilizzazione in seno a una disciplina, detta appunto teoria dei g., consente di affrontare e risolvere problemi particolari non solo in matematica ma anche in varî campi delle scienze applicate quali la chimica, la meccanica statistica, la teoria economica dei trasporti, i controlli automatici, ecc., schematizzando il flusso di segnali, informazioni, quantità, ecc., oppure l’insieme di relazioni sequenziali che legano tra loro varie attività, varî organi, ecc. Si dice g. completo o incompleto a seconda che ogni vertice sia collegato a ciascuno degli altri da un lato oppure no; g. complementare, quello costituito dagli spigoli che occorre aggiungere a un grafo dato per renderlo completo (se, per es., i vertici di un grafo rappresentano i giocatori partecipanti a un torneo e i lati del grafo le partite già disputate, il grafo complementare indica le partite ancora da disputare: particolari grafi incompleti sono gli alberi); g. di Eulero, ogni grafo che si possa percorrere interamente senza interruzioni e senza passare più di una volta su uno stesso spigolo.