# Graf dirigit

Un graf dirigit o dígraf és un tipus de graf en el qual les arestes tenen un sentit definit, a diferència del graf no dirigit, en què les arestes són relacions simètriques i no apunten a cap lloc.
De vegades, un dígraf s’anomena dígraf simple per distingir-lo del cas general del multigraf dirigit, on els arcs constitueixen un multiconjunt, en lloc d’un conjunt. En aquest cas, pot haver-hi més d’un arc que unisca dos vèrtexs en la mateixa direcció, distingint-se mútuament per la seva identitat, pel seu tipus (per exemple, un tipus d’arc representa relacions d’amistat mentre l’altre tipus representa missatges enviats recentment entre el nodes), o per un atribut com la seva importància o pes. Sovint també es considera que en un simple dígraf no es permeten els bucles.

## Definició formal

Com en el graf generalitzat, el graf dirigit està definit per un parell de conjunts $G=(V,E)$, on:
* $V\neq \emptyset$, un conjunt no buit d'objectes simples anomenats vèrtexs o nodes.
* $E\subseteq \{(a,b)\in V\times V:a\neq b\}\,$ és un conjunt de parells d'elements de $V\,$ anomenats arestes o arcs, on per definició un arc va del primer node $a$ al segon node $b$ dins del parell.
* Un arc $e=(x,y)$ es considera dirigit des d'$x$ a $y$. Una altra notació vàlida és $e=<x,y>$. En ambdós casos, el vèrtex $x$ compleix un paper d'«emissor» i el vèrtex $y$ un de «receptor».

## Propietats

Sigui $n=|V|$ El nombre de nodes d'un gràfic dirigit, que com a màxim pot tenir $n^{2}$ arestes i $n(n-1)$ en cas que s’excloguin els bucles.

## Conceptes relacionats

Si hi ha un camí fet per un o més arcs que uneix $x$ amb $y$, aleshores $y$ es diu successor d'$x$, i $x$ s’anomena predecessor d'$y$. Donat una aresta $(x,y)$, el vèrtex $y$ també s’anomena successor directe d'$x$;
En correspondència, un predecessor directe d'$y$ es diu $x$. L’arc $(y,x)$ s’anomena arc invertit d'$(x,y)$.
Un graf dirigit s’anomena simètric si, per a qualsevol arc que pertany a $G$, l’arc invertit corresponent també pertany a $G$. Un graf dirigit simètric i sense bucles equival a un gràfic no dirigit; N’hi ha prou de substituir cada parell d’arcs dirigits per un únic arc no dirigit.
S’obté una orientació d’un graf simple no dirigit mitjançant l’assignació d’una orientació a cadascun dels arcs existents. Un graf dirigit integrat d'aquesta manera s'anomena graf orientat. Una forma de distingir entre un graf senzill i un graf orientat és que si $x$ i $y$ són vèrtexs un graf simple dirigit permet tant $(x,y)$ com $(y,x)$ entre els seus arcs, mentre que a un graf orientat sol una de las dos possibilitats es admesa.
Un dígraf ponderat és una dígraf en el qual hi ha pesos associats a cadascun dels arcs, anàlegs al graf ponderat. Un dígraf ponderat en el context de la teoria de grafs s’anomena xarxa.
La matriu adjacència d’un dígraf (amb bucles i arcs mòbils permesos) és una matriu composta per valors sencers, on les taxes de columnes i files corresponen a les identitats dels vèrtexs $v$. Un element d'aquesta matriu, un $a_{ij}$ representa el nombre d'arcs existents entre els nodes $i$ i $j$. Un element de la diagonal d'aquesta matriu, un $a_{ii}$ representa el nombre de bucles que existeixen al node $i$. La matriu d'adjacència d’un dígraf és una representació única del dígraf, tret de possibles permutacions de les files i columnes.
Una altra representació comuna d’un dígraf és la matriu d'incidència.

## Bibliografia

* Wasserman, Stanley; Faust, Katherine. Centro de Investigaciones Sociológicas. Análisis de redes sociales: Métodos y aplicaciones, 2013. ISBN 978-84-7476-631-8. OCLC 871814053.

## Referències

* ↑ Bang-Jensen,Gutin,2000. Diestel,2005, Section 1.10. Bondy,Murty,1976, Section 10.
* ↑ Wasserman & Faust 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
* ↑ Weisstein, Eric W., «SimpleDirectedGraph» a MathWorld (en anglès).
* ↑ Diestel,2005, Section 1.10.
* ↑ Weisstein, Eric W., «Oriented Graph» a MathWorld (en anglès).