¿Por qué son importantes los gráficos dirigidos?

18

Hemos estado leyendo sobre algoritmos para MST, conectividad fuerte, enrutamiento, etc. en gráficos dirigidos.

También recientemente, la gente ha estado investigando algoritmos dinámicos y tolerantes a fallas para gráficos dirigidos.

Pero me preguntaba si hay aplicaciones prácticas en las que la red gráfica subyacente esté "Dirigida". Aparte de las redes sociales, todos los problemas en los que podría pensar, como la red ferroviaria / vial, la red de Internet, etc., se refieren solo a gráficos no dirigidos.

Edición 1: entiendo que estos pueden usarse para modelar algunos escenarios donde se dirigen los enlaces, pero me preguntaba con qué frecuencia ocurren estos escenarios en el mundo real y qué tan importante es el estudio de la tolerancia a fallas para los gráficos dirigidos.

graphs graph-theory fault-tolerance chile
fuente
66
Dos de las clases más famosas de gráficos dirigidos en toda la informática son el árbol y el DAG (gráfico acíclico dirigido). El árbol se usa en muchas cosas (por ejemplo, árboles genealógicos, jerarquías); El DAG puede hacer versiones más sofisticadas de esos. Los DAG se usan esencialmente cuando tiene un conjunto de entidades que tienen dependencias entre sí. Cuando su problema tiene un componente de "tiempo" o "paso a paso", la dirección representa esa marcha inexorable de progreso. Puede ver DAG en diagramas de flujo, software de administración de paquetes y formularios SSA de representación intermedia de compiladores.
Iwillnotexist Idonotexist
2
OK, ¿cuál es tu pregunta real? ¿Desea saber por qué los gráficos dirigidos son importantes o por qué es importante la tolerancia a fallas en los gráficos dirigidos? Esas son dos preguntas completamente separadas.
David Richerby
2
Sus ejemplos, aunque físicamente "no dirigidos" en la implementación, todavía con frecuencia tienen gráficos dirigidos que operan lógicamente sobre ellos. Por ejemplo, los trenes no viajan bidireccionalmente: van en un sentido u otro en un horario. Digamos que uno no programa los trenes, sino que solo programa pasajeros. Entonces, esa persona está interesada en un gráfico dirigido, a pesar del hecho arbitrario de que los trenes pueden viajar teóricamente en cualquier dirección en un ferrocarril.
Darren Ringer
55
chyle: Las redes ciertamente pueden beneficiarse de ser representadas por un gráfico dirigido. La mayoría de las conexiones domésticas a Internet son asimétricas. Los enlaces ascendentes y descendentes pueden tener propiedades completamente diferentes (ancho de banda, latencia, pérdida de paquetes, etc.)
Alexander - Restablecer Mónica el
1
No sé sobre todos los demás, pero mi árbol genealógico es un dígrafo. No soy el padre de mi madre.

Respuestas:

36

Recordando que un gráfico dirigido es un gráfico donde los bordes tienen una dirección asociada con ellos.

Usando un gráfico dirigido puede representar relaciones asimétricas entre nodos, mientras que en un gráfico no dirigido solo podemos representar relaciones simétricas .

Prácticamente, usando un gráfico dirigido puede representar:

  • Redes de carreteras (usando un gráfico dirigido puede representar la dirección de las calles);
  • hipervínculos que conectan páginas web ;
  • dependencias en módulos de software ;
  • relaciones presa-depredador ;
  • determinista autómata finito .

Además de estos ejemplos clásicos, puede representar muchos otros escenarios del mundo real (comercio financiero, programación, enfermedades infecciosas, citas, flujo de control, etc.) que necesitan una relación ordenada [1] .

darioSka
fuente
44
Gran respuesta. Creo que OP está olvidando que cuando tienes una calle, en realidad tienes dos calles (una para cada dirección, generalmente perfectamente paralela). Se pueden representar como un gráfico simple, pero los gráficos dirigidos agregan información esencial al modelo.
ecc
Me gusta esto y me doy cuenta de que esta respuesta es cuidadosa al decir páginas web conectadas con hipervínculos, lo que excluye el uso de la función Atrás. ;-)
SDsolar
Para poner el comentario de @ ecc en la lengua vernácula, tiene dos nodos conectados por dos bordes. Cada borde se dirige opuesto al otro. Se ve a menudo en diagramas de estado deterministas. Para las calles, se reduciría a un solo borde, ya sea dirigido (unidireccional) o no dirigido.
SDsolar
44
@ecc también, de donde soy (California), tenemos calles de sentido único
k_g
5

Los gráficos dirigidos existen. Como se menciona en los comentarios, los Gráficos Acíclicos Dirigidos (DAG), en particular, son tremendamente útiles en muchas tareas computacionales como la compilación de código.

Además, vale la pena señalar que la mayoría de los algoritmos de gráficos dirigidos se pueden usar en el caso no dirigido simplemente reemplazando cada borde no dirigido con dos bordes dirigidos. El doble de esto, tratar de hacer un gráfico dirigido a partir de un gráfico no dirigido, no se puede hacer para la mayoría de los algoritmos.

Cort Ammon - Restablece a Monica
fuente
3

Los comienzos de la clasificación topológica (una operación fundamental en gráficos acíclicos dirigidos) se encuentran en redes de dependencias en la gestión de proyectos, específicamente el método PERT . Kahn y Lasser citan PERT en sus documentos y basan sus ejemplos en ellos, por ej.

Se puede solicitar una red PERT de 30,000 actividades en menos de una hora de tiempo de máquina.

La programación de trabajos en línea todavía se realiza con este tipo de red; por ejemplo, un sistema ETL programa trabajos para que se ejecuten solo después de que se hayan ejecutado los trabajos que proporcionan sus datos de entrada.

KWillets
fuente
2

Respuesta: Del OP deduzco que la pregunta está realmente relacionada con los ODS (Gráficos Dirigidos Firmados). Así que aquí está mi respuesta que aborda los gráficos dirigidos básicos y luego conduce a los ODS.

Los gráficos dirigidos se utilizan ampliamente en el análisis de árbol de fallas en sistemas industriales. A medida que elimina las causas de una falla, sigue el gráfico dirigido para explorar otras posibilidades.

Los gráficos dirigidos se utilizan para evitar la revisión contraproducente de los nodos que se han eliminado efectivamente. En el diagnóstico de fallas, a menudo el tiempo para la restauración del servicio es crítico. En sistemas industriales complejos, siempre hay un árbol paralelo basado en el tiempo que puede conducir al apagado total del sistema si la falla no se corrige dentro de varias limitaciones de tiempo. Ir y venir sería más probable que conduzca a una falla total, lo que puede causar operaciones de restauración que requieren mucho más tiempo (como el drenaje de tanques y tuberías para reiniciar una refinería).

Es como cortar una rama de árbol: no es necesario volver al tronco cuando intentas encontrar una sola rama.

Los ODS tienen la propiedad adicional de brindar orientación basada en probabilidades o umbrales para ayudar a tomar decisiones a medida que se recorre el árbol.

Aquí hay un enlace a un buen libro sobre el tema, llamado Detección y diagnóstico de fallas en sistemas industriales (página 224), donde describe los beneficios del diagnóstico basado en SDG:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

SDsolar
fuente