Gráfico dirigido vs no dirigido
Un gráfico es una estructura matemática que se compone de un conjunto de vértices y aristas. Un gráfico representa un conjunto de objetos (representados por vértices) que están conectados a través de algunos enlaces (representados por bordes). Usando notaciones matemáticas, un gráfico se puede representar por G, donde G = (V, E) y V es el conjunto de vértices y E es el conjunto de aristas. En un gráfico no dirigido no hay dirección asociada con los bordes que conectan los vértices. En un gráfico dirigido hay una dirección asociada con los bordes que conectan los vértices.
Gráfico no dirigido
Como se mencionó anteriormente, un gráfico no dirigido es un gráfico en el que no hay dirección en los bordes que unen los vértices del gráfico. La Figura 1 muestra un gráfico no dirigido con un conjunto de vértices V = {V1, V2, V3}. El conjunto de aristas en el gráfico anterior se puede escribir como V = {(V1, V2), (V2, V3), (V1, V3)}. También se puede notar que no hay nada que impida escribir el conjunto de aristas como V = {(V2, V1), (V3, V2), (V3, V1)} ya que las aristas no tienen dirección. Por lo tanto, las aristas de un gráfico no dirigido no son pares ordenados. Ésta es la característica principal de un gráfico no dirigido. Los gráficos no dirigidos se pueden utilizar para representar relaciones simétricas entre objetos que están representados por vértices. Por ejemplo, una red de carreteras de dos vías que conecta un conjunto de ciudades se puede representar mediante un gráfico no dirigido. Las ciudades se pueden representar mediante los vértices en el gráfico y los bordes representan las carreteras de dos vías que conectan las ciudades.
Gráfico dirigido
Un gráfico dirigido es un gráfico en el que las aristas del gráfico que unen los vértices tienen una dirección. La Figura 2 muestra un gráfico dirigido con un conjunto de vértices V = {V1, V2, V3}. El conjunto de aristas en el gráfico anterior se puede escribir como V = {(V1, V2), (V2, V3), (V1, V3)}. Los bordes de un gráfico no dirigido son pares ordenados. Formalmente, la arista e en una gráfica dirigida se puede representar mediante el par ordenado e = (x, y) donde x es el vértice que se llama origen, fuente o punto inicial de la arista e, y el vértice y se llama término, vértice de terminación o punto terminal. Por ejemplo, una red de carreteras que conecta un conjunto de ciudades utilizando carreteras de un solo sentido se puede representar mediante un gráfico no dirigido. Las ciudades se pueden representar por los vértices en el gráfico y los bordes dirigidos representan las carreteras que conectan las ciudades considerando la dirección en la que fluye el tráfico en la carretera.
¿Cuál es la diferencia entre el gráfico dirigido y el gráfico no dirigido?
En un gráfico dirigido, una arista es un par ordenado, donde el par ordenado representa la dirección de la arista que une los dos vértices. Por otro lado, en un gráfico no dirigido, una arista es un par desordenado, ya que no hay una dirección asociada con una arista. Se pueden usar gráficos no dirigidos para representar relaciones simétricas entre objetos. El grado de entrada y de salida de cada nodo en un gráfico no dirigido es igual, pero esto no es cierto para un gráfico dirigido. Cuando se usa una matriz para representar un gráfico no dirigido, la matriz siempre se convierte en un gráfico simétrico, pero esto no es cierto para un gráfico dirigido. Un gráfico no dirigido se puede convertir en un gráfico dirigido reemplazando cada borde con dos bordes dirigidos en dirección opuesta. Sin embargo, no es posible convertir un gráfico dirigido en un gráfico no dirigido.
