Tratar gráficos não direcionados como uma subcategoria de gráficos direcionados

10

Grosso modo, um gráfico não direcionado é muito semelhante a um gráfico direcionado, onde para cada aresta (v, w), sempre há uma aresta (w, v). Isso sugere que pode ser aceitável exibir gráficos não direcionados como um subconjunto de gráficos direcionados (talvez com uma restrição adicional de que a adição / exclusão de arestas só pode ser feita em pares correspondentes).

No entanto, os livros didáticos geralmente não seguem esse tratamento e preferem definir gráficos não direcionados como um conceito separado, em vez de uma subcategoria de gráficos direcionados. Há alguma razão para isso?

graphs terminology max
fonte
2
Observe que também existem "gráficos mistos": um gráfico onde as bordas podem ser direcionadas ou não. Nesse caso, um par de arestas direcionadas não é o mesmo que uma aresta não direcionada entre dois nós. Por exemplo: considere ruas: você pode ter um par de ruas de mão única entre dois pontos em direções opostas ou uma única rua de mão dupla. Isso é importante em alguns casos: por exemplo, você não deseja que um dispositivo de navegação diga ao usuário para fazer uma inversão de marcha entre duas ruas de mão única, se houver uma barreira no meio, embora seja possível fazer isso em um única via de mão dupla.
Bakuriu 27/01

Respostas:

8

Você está absolutamente correto; essa é uma maneira perfeitamente válida de visualizar gráficos não direcionados.

Às vezes, em gráficos não direcionados, algumas coisas se tornam mais fáceis e limpas para se pensar. Por exemplo, você não precisa se preocupar com a diferença entre componentes fracamente conectados e fortemente conectados em gráficos não direcionados. Algoritmos para gráficos não direcionados às vezes podem ser mais eficientes ou mais simples do que se aplicássemos o algoritmo correspondente para gráficos direcionados.

Assim: talvez alguns livros escolares sigam esse tratamento, pois permitem que eles introduzam um problema primeiro no contexto (mais fácil) de gráficos não direcionados e depois generalizem para o caso (mais difícil) de gráficos direcionados. Isso é apenas especulação.

DW
fonte
3

Consulte esta página para exemplos de problemas para os quais a forma de gráfico não direcionado é realmente mais difícil que a forma de gráfico direcionado. Isso inclui, por exemplo, encontrar um ciclo de peso negativo e contar o número de ciclos eulerianos. Para mim, esses problemas parecem ser mais difíceis em gráficos não direcionados, porque parte da tarefa pode ser enquadrada como, de alguma forma, a escolha da "direção" certa para cada aresta - o que, obviamente, já está "feito para nós" quando o gráfico é direcionado.

j_random_hacker
fonte
11
Oh, certo. Por exemplo, o ciclo euleriano, quando definido em termos de gráficos direcionados, precisaria exigir que "não seja usada mais de uma aresta de cada par (v, w), (w, v)" - criando a idéia de representar um gráfico não direcionado como um dígrafo menos atraente.
max
0

É difícil motivar algo muito geral do nada; isso pode tornar as provas e os livros mais simples, mas não necessariamente mais fáceis de entender e seguir intuitivamente.
As pessoas geralmente acham mais intuitivo aprender um conceito simples e, em seguida, generalizá-lo para algo mais abstrato, em vez de definir algum conceito super-generalizado e abstrato e instanciar seus casos particulares. Este é provavelmente um desses casos.

user541686
fonte