Digrafo (matematica)

Da Wikipedia, l'enciclopedia libera.

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.

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 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 nondeterministici. 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.

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Bibliografia[modifica | modifica sorgente]

  • (EN) K. Thulasiraman, M. N. S. Swamy (1992): Graphs: Theory and Algorithms, J.Wiley
matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica