Digrafo (matematica)

In matematica, e in particolare in matematica discreta, per digrafo si intende la struttura relazionale di base, costituita da un insieme finito detto insieme dei nodi e da collegamenti orientati tra tali nodi. Termini equivalenti sono grafo diretto (digrafo è una sua contrazione) e grafo orientato.

Descrizione

Formalmente si definisce digrafo una struttura della forma $\,D=\langle Q,U\rangle$ con Q insieme finito detto insieme dei nodi di D e $U\subseteq Q\times Q$ detto insieme degli archi di D.

Un grafo orientato può essere rappresentato graficamente disegnando ogni nodo con un cerchio e ogni arco con una freccia; un arco "esce" da un nodo ed "entra" in un altro (quello indicato dalla freccia). Da ogni nodo possono uscire più archi.

Un digrafo è una relazione finita accompagnata da un insieme il cui quadrato cartesiano la contiene. Ai digrafi quindi si possono applicare tutte le distinzioni, tutte le proprietà e tutte le costruzioni introdotte per le relazioni e che hanno senso per le relazioni finite. Si possono quindi distinguere i digrafi riflessivi, antiriflessivi, simmetrici, antisimmetrici, transitivi, di equivalenza, ordinati, graduati, semireticolati, reticolati, booleani, funzionali, permutativi, involutori, ... .

Un digrafo si può considerare un arricchimento di un grafo non orientato ottenuto sostituendo ogni suo spigolo {p,q} che non sia un cappio con uno o due archi: {p,q} si può rimpiazzare con (p,q), con (q,p) o con entrambi questi archi. Di conseguenza tutte le distinzioni, le proprietà e le costruzioni sui grafi non orientati possono essere adattate ai digrafi, in genere accompagnandole con apportune distinzioni.

Come i grafi non orientati, i digrafi vengono utilmente presentati attraverso raffigurazioni piane.

Un digrafo $\,D=\langle Q,U\rangle$ viene individuato dalla sua matrice delle adiacenze, matrice quadrata binaria che corrisponde alla funzione indicatrice di U come sottoinsieme di $Q\times Q$. Dunque lo studio dei digrafi, cioè lo studio delle relazioni finite, equivale allo studio delle matrici quadrate binarie.

I digrafi possono essere arricchiti in molti modi, spesso suggeriti dalle loro molteplici applicazioni. Si hanno innanzitutto digrafi con i nodi e/o gli archi muniti di etichette distintive o di numeri (digrafi colorati, digrafi pesati, sui nodi e/o sugli archi, ...). Anche questi primi arricchimenti trovano applicazioni in campi che vanno dalla chimica alla fisica delle particelle, dai problemi di trasporto alla meccanica strutturale, dalla linguistica alla geografia.

Due arricchimenti primari portano alle strutture di multidigrafo e di pluridigrafo. Ulteriori arricchimenti di questi portano ai vari tipi di automi deterministici e non deterministici. Altri arricchimenti portano agli schemi di programma e ai diagrammi di flusso, cioè agli algoritmi. Mediante digrafi arricchiti si possono utilmente schematizzate le reti di computer e le reti di pagine Web che costituiscono i siti, i domini o l'intera Rete globale.

Vengono anche considerati varianti dei digrafi che presentano una infinità numerabile di nodi e che qui chiamiamo digrafi infiniti.

Bibliografia

• (EN) K. Thulasiraman, M. N. S. Swamy (1992): Graphs: Theory and Algorithms, John Wiley & Sons

Voci correlate

• Grafo
• Algoritmo di Edmonds
• Quiver

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul digrafo

Collegamenti esterni

• (EN) directed graph, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti Directed graphs, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Directed Graph, su MathWorld, Wolfram Research.
• (EN) Graph, oriented, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.