Digrafo (matematica)

Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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 ${\displaystyle \,D=\langle Q,U\rangle }$ con Q insieme finito detto insieme dei nodi di D e ${\displaystyle 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 ${\displaystyle \,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 ${\displaystyle 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.

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

• Grafo
• Algoritmo di Edmonds
• Quiver

• Wikimedia Commons contiene immagini o altri file sul digrafo

• (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.

V · D · M Combinatoria
Orientamento generale	Combinatoria · Storia della combinatoria · Matematica discreta · Sezione 05-XX di MSC
Nozioni introduttive	Permutazioni · Disposizioni · Combinazioni · Coefficienti binomiali · Partizioni di interi · Partizioni di insiemi finiti - Identità combinatorie e biiezioni · Principio dei cassetti
Configurazioni	Quadrati latini · Quadrati magici · Disegni a blocchi · Geometrie finite · Matroidi - Tassellazioni · Polimini
Teoria dei grafi	Alberi · Cammini sui grafi (euleriani, hamiltoniani) · Connessione nei grafi - Grafi planari · Colorazione dei grafi e teorema dei quattro colori) · Ipergrafi · Grafi e gruppi · Digrafo · Flussi su grafi · Passeggiate aleatorie su grafi · Omomorfismo fra grafi · Algoritmi sui grafi
Combinatoria algebrica	Tavola di Young · Funzioni simmetriche - Serie formale di potenze · Funzioni generatrici · Polinomi ortogonali · Azioni di un gruppo su strutture combinatorie - Aspetti combinatorici dell'algebra commutativa
Altre aree	Calcolo umbrale (sequenze polinomiali di tipo binomiale · sequenze di Sheffer) - Combinatoria estremale

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica