Diferença entre gráfico direcionado e não direcionado

Gráfico Dirigido vs Não Dirigido

Um gráfico é uma estrutura matemática composta por um conjunto de vértices e arestas. Um gráfico representa um conjunto de objetos (representados por vértices) que são conectados através de alguns links (representados por arestas). Usando notações matemáticas, um gráfico pode ser representado por G, onde G = (V, E) e V é o conjunto de vértices e E é o conjunto de arestas. Em um gráfico não direcionado, não há direção associada às arestas que conectam os vértices. Em um gráfico direcionado, há uma direção associada às arestas que conectam os vértices.

Gráfico não direcionado

Como mencionado anteriormente, um gráfico não direcionado é um gráfico no qual não há direção nas arestas que vinculam os vértices no gráfico. A Figura 1 mostra um gráfico não direcionado com um 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). Também pode ser observado que não há nada que impeça a gravação do conjunto de arestas como V = (V2, V1), (V3, V2), (V3, V1), pois as arestas não têm uma direção. Portanto, as arestas em um gráfico não direcionado não são pares ordenados. Essa é a principal característica de um gráfico 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 bidirecional 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 estradas de duas vias que conectam as cidades.

Gráfico Dirigido

Um gráfico direcionado é um gráfico no qual as arestas do gráfico que vinculam os vértices têm uma direção. A Figura 2 mostra um gráfico direcionado com um 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 de um gráfico não direcionado são pares ordenados. Formalmente, a aresta e em um gráfico direcionado pode ser representada pelo par ordenado e = (x, y) em que x é o vértice chamado origem, fonte ou ponto inicial da aresta e, e o vértice y é chamado terminal , vértice final ou ponto terminal. Por exemplo, uma rede de estradas 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 gráfico e as arestas direcionadas representam as estradas que conectam as cidades, considerando a direção em que o tráfego flui na estrada.

Qual é a diferença entre o gráfico direcionado e o gráfico não direcionado?

Em um gráfico direcionado, uma aresta é um par ordenado, em que o par ordenado representa a direção da aresta que liga os dois vértices. Por outro lado, em um gráfico 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 gráfico não direcionado é igual, mas isso não é verdade para um gráfico 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 gráficos direcionados. Um gráfico não direcionado pode ser convertido em um gráfico direcionado substituindo cada aresta por duas arestas direcionadas na direção oposta. No entanto, não é possível converter um gráfico direcionado em um gráfico não direcionado.