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.

Un graf simple dirigit

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 ${\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]

Propietats

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]

Conceptes relacionats

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.

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.