Gráfico Dirigido x Não Dirigido
Um grafo é uma estrutura matemática composta por um conjunto de vértices e arestas. Um grafo representa um conjunto de objetos (representados por vértices) que estão conectados por meio de alguns links (representados por arestas). Usando notações matemáticas, um grafo pode ser representado por G, onde G=(V, E) e V é o conjunto de vértices e E é o conjunto de arestas. Em um grafo não direcionado não há direção associada às arestas que conectam os vértices. Em um grafo direcionado há uma direção associada às arestas que conectam os vértices.
Gráfico não direcionado
Como mencionado anteriormente, um grafo não direcionado é um grafo no qual não há direção nas arestas que ligam os vértices no grafo. A Figura 1 mostra um grafo não direcionado com conjunto de vértices V={V1, V2, V3}. O conjunto de arestas no gráfico acima pode ser escrito como V={(V1, V2), (V2, V3), (V1, V3)}. Pode-se notar também que não há nada que impeça escrever o conjunto de arestas como V={(V2, V1), (V3, V2), (V3, V1)} já que as arestas não têm direção. Portanto, as arestas em um grafo não direcionado não são pares ordenados. Esta é a principal característica de um grafo não direcionado. Gráficos não direcionados podem ser usados para representar relacionamentos simétricos entre objetos que são representados por vértices. Por exemplo, uma rede rodoviária de duas vias que conecta um conjunto de cidades pode ser representada usando um gráfico não direcionado. As cidades podem ser representadas pelos vértices no gráfico e as arestas representam as vias de mão dupla que ligam as cidades.
Gráfico Dirigido
Um grafo direcionado é um grafo no qual as arestas do grafo que ligam os vértices têm uma direção. A Figura 2 mostra um grafo direcionado com conjunto de vértices V={V1, V2, V3}. O conjunto de arestas no gráfico acima pode ser escrito como V={(V1, V2), (V2, V3), (V1, V3)}. As arestas em um grafo não direcionado são pares ordenados. Formalmente, a aresta e em um grafo direcionado pode ser representada pelo par ordenado e=(x, y) onde x é o vértice que é chamado de origem, fonte ou ponto inicial da aresta e, e o vértice y é chamado de terminal, vértice final ou ponto terminal. Por exemplo, uma rede rodoviária que conecta um conjunto de cidades usando estradas de sentido único pode ser representada usando um gráfico não direcionado. As cidades podem ser representadas pelos vértices no grafo e as arestas direcionadas representam as vias que ligam as cidades considerando a direção em que o tráfego flui na via.
Qual é a diferença entre o gráfico direcionado e o gráfico não direcionado?
Em um grafo direcionado uma aresta é um par ordenado, onde o par ordenado representa a direção da aresta que liga os dois vértices. Por outro lado, em um grafo não direcionado, uma aresta é um par não ordenado, pois não há direção associada a uma aresta. Gráficos não direcionados podem ser usados para representar relacionamentos simétricos entre objetos. O grau de entrada e saída de cada nó em um grafo não direcionado é igual, mas isso não é verdade para um grafo direcionado. Ao usar uma matriz para representar um gráfico não direcionado, a matriz sempre se torna um gráfico simétrico, mas isso não é verdade para um gráfico direcionado. Um grafo não direcionado pode ser convertido em um grafo direcionado substituindo cada aresta por duas arestas direcionadas indo em direções opostas. No entanto, não é possível converter um gráfico direcionado em um gráfico não direcionado.
