Diferença Entre Gráfico Direcionado E Não Direcionado

2024 Autor: Mildred Bawerman | [email protected]. Última modificação: 2023-12-16 08:41

Gráfico direcionado vs não direcionado

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 por meio 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 ligam os vértices do gráfico. A Figura 1 representa um gráfico 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 nada impede a escrita do conjunto de arestas como V = {(V2, V1), (V3, V2), (V3, V1)} uma vez que as arestas não têm direção. Portanto, as arestas em um gráfico não direcionado não são pares ordenados. Esta é a principal característica de um gráfico não direcionado. Os 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 de estradas de mão dupla 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 mão dupla que conectam as cidades.

Gráfico Direcionado

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 representa um gráfico 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 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) onde x é o vértice que é chamado de origem, fonte ou o ponto inicial da aresta e, e o vértice y é chamado de término, vértice de terminação ou ponto terminal. Por exemplo, uma rede de estradas que conecta um conjunto de cidades usando estradas de mão única 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 que o tráfego flui na estrada.

Qual é a diferença entre Directed Graph e Undirected Graph?

Em um gráfico 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 gráfico não direcionado, uma aresta é um par não ordenado, uma vez que 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 de 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 indo na direção oposta. No entanto, não é possível converter um gráfico direcionado em um gráfico não direcionado.