Tratar gráficos no dirigidos como una subcategoría de gráficos dirigidos

10

Aproximadamente, un gráfico no dirigido es muy similar a un gráfico dirigido donde para cada borde (v, w), siempre hay un borde (w, v). Eso sugiere que podría ser aceptable ver gráficos no dirigidos como un subconjunto de gráficos dirigidos (tal vez con una restricción adicional de que agregar / eliminar bordes solo se puede hacer en pares coincidentes).

Sin embargo, los libros de texto generalmente no siguen este tratamiento, y prefieren definir gráficos no dirigidos como un concepto separado, en lugar de una subcategoría de gráficos dirigidos. ¿Hay alguna razón para eso?

graphs terminology max
fuente
2
Tenga en cuenta que también existen "gráficos mixtos": un gráfico donde los bordes se pueden dirigir o no. En este caso, un par de aristas dirigidas no es lo mismo que una arista no dirigida entre dos nodos. Por ejemplo: considere calles: puede tener un par de calles de un sentido entre dos puntos que van en direcciones opuestas, o una sola calle de dos sentidos. Esto es importante en algunos casos: por ejemplo, no desea que un dispositivo de navegación le diga a un usuario que realice un giro en U entre dos calles de sentido único si hay una barrera en el medio, mientras que es posible hacerlo en un sola calle de doble sentido.
Bakuriu

Respuestas:

8

Tienes toda la razón; Esa es una forma perfectamente válida de ver gráficos no dirigidos.

A veces, en gráficos no dirigidos, algunas cosas se vuelven más fáciles y más limpias para razonar. Por ejemplo, no tiene que preocuparse por la diferencia entre componentes débilmente conectados o fuertemente conectados en gráficos no dirigidos. Los algoritmos para gráficos no dirigidos a veces pueden ser más eficientes o más simples que si tuviéramos que aplicar el algoritmo correspondiente para gráficos dirigidos.

Entonces: quizás algunos libros de texto eligen seguir este tratamiento porque les permite introducir un problema primero en el contexto (más fácil) de los gráficos no dirigidos, y luego generalizar el caso (más difícil) de los gráficos dirigidos. Eso es solo especulación.

DW
fuente
3

Consulte esta página para ver ejemplos de problemas para los cuales la forma de gráfico no dirigido es realmente más difícil que la forma de gráfico dirigido. Estos incluyen, por ejemplo, encontrar un ciclo de peso negativo y contar el número de ciclos de Eulerian. Para mí, estos problemas parecen ser más difíciles en los gráficos no dirigidos porque parte de la tarea puede enmarcarse de alguna manera eligiendo la "dirección" correcta para cada borde, que por supuesto "ya está hecho para nosotros" cuando se dirige el gráfico.

j_random_hacker
fuente
1
Correcto. Por ejemplo, el ciclo de Eulerian cuando se define en términos de gráficos dirigidos, tendría que requerir que "no se use más de un borde de cada par (v, w), (w, v)", lo que hace que la idea de representar un gráfico no dirigido como un dígrafo menos atractivo.
max
0

Es difícil motivar algo muy general de la nada; puede hacer que las pruebas y los libros de texto sean más simples, pero no necesariamente más fáciles de entender y seguir intuitivamente.
Por lo general, a las personas les resulta más intuitivo aprender un concepto simple y luego generalizarlo a algo más abstracto, en lugar de definir algún concepto súper generalizado y abstracto y luego instanciar sus casos particulares. Este es probablemente uno de esos casos.

usuario541686
fuente