Graf dirigit

Un graf dirigit o dígraf és un tipus de graf en el qual les arestes tenen un sentit definit,^[1] 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.

Com en el graf generalitzat, el graf dirigit està definit per un parell de conjunts ${\displaystyle G=(V,E)}$, on:

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

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

Si hi ha un camí fet per un o més arcs que uneix ${\displaystyle x}$ amb ${\displaystyle y}$, aleshores ${\displaystyle y}$ es diu successor d'${\displaystyle x}$, i ${\displaystyle x}$ s’anomena predecessor d'${\displaystyle y}$. Donat una aresta ${\displaystyle (x,y)}$, el vèrtex ${\displaystyle y}$ també s’anomena successor directe d'${\displaystyle x}$;

En correspondència, un predecessor directe d'${\displaystyle y}$ es diu ${\displaystyle x}$. L’arc ${\displaystyle (y,x)}$ s’anomena arc invertit d'${\displaystyle (x,y)}$.

Un graf dirigit s’anomena simètric si, per a qualsevol arc que pertany a ${\displaystyle G}$, l’arc invertit corresponent també pertany a ${\displaystyle 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 ${\displaystyle x}$ i ${\displaystyle y}$ són vèrtexs un graf simple dirigit permet tant ${\displaystyle (x,y)}$ com ${\displaystyle (y,x)}$ entre els seus arcs, mentre que a un graf orientat sol una de las dos possibilitats es admesa.^[4][5]

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 ${\displaystyle v}$. Un element d'aquesta matriu, un ${\displaystyle a_{ij}}$ representa el nombre d'arcs existents entre els nodes ${\displaystyle i}$ i ${\displaystyle j}$. Un element de la diagonal d'aquesta matriu, un ${\displaystyle a_{ii}}$ representa el nombre de bucles que existeixen al node ${\displaystyle 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.

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