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 aristas). Usando notaciones matemáticas, un gráfico puede ser representado 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 grafo dirigido hay una dirección asociada con las aristas que conectan los vértices.
Gráfica no dirigida
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 tanto, las aristas de un grafo no dirigido no son pares ordenados. Esta es la principal característica de un grafo no dirigido. Los gráficos no dirigidos se pueden utilizar para representar relaciones simétricas entre objetos representados por vértices. Por ejemplo, una red de carreteras de dos sentidos que conecta un conjunto de ciudades se puede representar mediante un gráfico no dirigido. Las ciudades se pueden representar mediante los vértices del gráfico y los bordes representan las carreteras de dos sentidos 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 en un gráfico no dirigido son pares ordenados. Formalmente, la arista e en un gráfico dirigido se puede representar mediante el par ordenado e=(x, y) donde x es el vértice que se denomina origen, fuente o punto inicial de la arista e, y el vértice y se denomina término, vértice terminal o punto terminal. Por ejemplo, una red de carreteras que conecta un conjunto de ciudades mediante carreteras de sentido único se puede representar mediante un gráfico no dirigido. Las ciudades pueden ser representadas por los vértices en el gráfico y los bordes dirigidos representan los caminos que conectan las ciudades considerando la dirección en que fluye el tráfico en el camino.
¿Cuál es la diferencia entre gráfico dirigido y 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. Los gráficos no dirigidos se pueden usar para representar relaciones simétricas entre objetos. El grado de entrada y 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 los gráficos dirigidos. Un gráfico no dirigido se puede convertir en un gráfico dirigido reemplazando cada borde con dos bordes dirigidos que van en dirección opuesta. Sin embargo, no es posible convertir un gráfico dirigido en un gráfico no dirigido.
