Representación mediante Grafos Dirigidos
?Qué es un grafo dirigido?.
Iniciaremos diciendo que un grafo dirigido consiste en un conjunto de vértices V y un conjunto de arcos, los vértices también pueden llamarse nodos o puntos, los arcos pueden llamarse arcos dirigidos o líneas dirigidas.
​
Los arcos son pares ordenados de vértices (A, B), donde A es la cola y B la cabeza del arco, y se expresa como A -> B.
La punta de la flecha esta en el vértice llamado cabeza y la cola en el vértices llamado cola se dice que el arco A -> B va de A a B y B es adyacente a A.
​
Representación de Grafos Dirigidos.
Para la representación de un grafo dirigido se pueden usar varias estructuras de datos, la selección dependerá de las operaciones que se les aplicara a los vértices. Una representación común de un grafo dirigido es la matriz de adyacencia.
Sea G= (V, A) un grafo, donde V= {1, 2, 3. . ., n}. La matriz de adyacencia para G es una matriz booleana de dimensión nxn, donde cada elemento [i, j] vale 1 si y solo si, existe un arco (i, j).
La principal desventaja de usar una matriz de adyacencia para representar un grafo dirigido es que requiere un espacio Ω (n2) aun si el grafo dirigido tiene menos de n2, Solo leer y examinar un matriz de adyacencia puede llevar un tiempo O (n2).
​
Para evitar esta desventaja se puede utilizar otro método común para un grafo dirigido, llanada representación con lista de adyacencia. El grafo está representado por un arreglo de listas de adyacencia. Sea G= (V, A) un grafo, donde V= {1, 2, 3. . ., n}. La lista de adyacencia para un vértice i es una lista, en algún orden, de todos los vértices adyacentes a i. Se puede representar G por medio de un arreglo H, donde H[i] es un apuntador a la lista de adyacencia del vértice i.
La representación mediante lista de adyacencia requiere una memoria proprocional al número de vértices más el número de arcos.Se usa cuando el número de arcos es mucho menor a n 2 . La desventaja es que podemos tomar un tiempo O(n) para determinar si hay un arco del vértice i al j.
​
A continuación les presentamos un vídeo que les puede ayudar a resolver mejor este tipo de ejercicios:
Conclución: Podemos concluir que la representación mediante los grafos dirigidos nos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
​
Bibliográfia: