Grafo dirigit

Archiu:Example of simple directed graph.svg

Grafo dirigit

Archiu:Directed.svg

Un grafo dirigit.

Un grafo dirigit o digrafo és un tipo de grafo en el qual les arestes tenen un sentit definit, a diferència del grafo no dirigit, en el qual les arestes són relacions simètriques i no apunten en cap sentit.

A voltes un digrafo és denominat digrafo simple per a distinguir-ho del cas general del multigrafo dirigit, a on els arcs constituïxen un multiconjunto, en lloc d'un conjunt. En este cas, pot haver més d'un arc que una dos vèrtiços en la mateixa direcció, distinguint-se entre sí per la seua identitat, pel seu tipo (per eixemple un tipo d'arc representa relacions d'amistat mentres que l'atre tipo representa mensages enviats recentment entre els nodos), o per un atribut com per eixemple la seua importància o pes. A sovint també es considera que en un digrafo simple no estan permesos els bucles.

Definició formal

De la mateixa manera que en el grafo generalisat, el grafo dirigit està definit per un parell de conjunts $G=(V,E)$, a on:

• $V\ne \mathrm{\varnothing }$, un conjunt no buit d'objectes simples cridats vèrtiços o nodos.
• $E\subseteq \{(a,b)\in V\times V:a\ne b\}$ és un conjunt de parells ordenats d'elements de $V$ denominats arestes o arcs, a on per definició un arc va del primer nodo (a) al segon nodo (b) dins del parell.

Un arc $e=(x,y)$ es considera dirigit des de $x$ cap a $y$. Una atra notació vàlida és $e=<x,y>$. En abdós casos, el vèrtiç $x$ complix un rol de «emissor» i el vèrtiç $y$ u de «receptor».

Propietats

Siga $n=|V|$ el número de nodos d'un grafo dirigit, est podrà a lo més tindre $n^2$ arestes, i $n(n-1)$ en cas que s'excloguen els bucles.

Bibliografia

• (2013) Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques. OCLC 871814053. ISBN 978-84-7476-631-8.