Pourquoi les graphiques dirigés sont-ils importants?

Nous avons lu sur les algorithmes pour MST, forte connectivité, routage, etc. dans les graphiques dirigés.

Récemment, des chercheurs ont également recherché des algorithmes dynamiques et tolérants aux pannes pour les graphiques dirigés.

Mais je me demandais s'il existe des applications pratiques où le réseau de graphes souligné est "dirigé". À part les réseaux sociaux, tous les problèmes auxquels je pourrais penser, comme le réseau ferroviaire / routier, le réseau Internet, etc., ne concernent que les graphiques non orientés.

Edit 1: Je comprends que ceux-ci peuvent être utilisés pour modéliser certains scénarios où les liens sont dirigés, mais je me demandais à quelle fréquence ces scénarios se produisent dans le monde réel, et quelle est l'importance de l'étude de la tolérance aux pannes pour les graphiques dirigés.

Rappelant qu'un graphe orienté est un graphe où les bords ont une direction associée.

En utilisant un graphe orienté, vous pouvez représenter des relations asymétriques entre les nœuds, tandis que dans un graphe non orienté, nous ne pouvons représenter que des relations symétriques .

En pratique, en utilisant un graphe orienté, vous pouvez représenter:

• Réseaux routiers (en utilisant un graphique dirigé, vous pouvez représenter la direction des rues);
• hyperliens reliant des pages Web ;
• dépendances dans les modules logiciels ;
• relations proie-prédateur ;
• automate fini déterministe .

Outre ces exemples classiques, vous pouvez représenter de nombreux autres scénarios du monde réel (commerce financier, planification, maladies infectieuses, citation, contrôle du flux, etc.) qui nécessitent une relation ordonnée [1] .

Des graphiques dirigés existent. Comme mentionné dans les commentaires, les graphiques acycliques dirigés (DAG), en particulier, sont extrêmement utiles dans de nombreuses tâches de calcul telles que la compilation de code.

De plus, il convient de noter que la plupart des algorithmes de graphe orienté peuvent être utilisés dans le cas non orienté simplement en remplaçant chaque bord non orienté par deux bords orientés. Le double de cela, essayer de faire un graphe orienté à partir d'un graphe non orienté, ne peut pas être fait pour la plupart des algorithmes.

Les débuts du tri topologique (opération fondamentale sur les graphes acycliques dirigés) résident dans les réseaux de dépendances en gestion de projet, notamment la méthode PERT . Kahn et Lasser citent tous les deux PERT dans leurs articles et basent leurs exemples dessus, par exemple

Un réseau PERT de 30 000 activités peut être commandé en moins d'une heure de temps machine.

La planification des travaux en ligne se fait toujours avec ce type de réseau; par exemple, un système ETL planifie l'exécution des travaux uniquement après l'exécution des travaux qui fournissent leurs données d'entrée.

Réponse: Du PO, je déduis que la question est en fait liée aux ODD (Graphes dirigés signés). Voici donc ma réponse qui aborde les graphiques dirigés de base puis mène aux ODD.

Les graphiques dirigés sont largement utilisés dans l'analyse des arbres de défaillances dans les systèmes industriels. Lorsque vous éliminez les causes d'un défaut, vous suivez le graphique dirigé pour explorer d'autres possibilités.

Des graphiques dirigés sont utilisés pour empêcher une révision contre-productive des nœuds qui ont été efficacement éliminés. Dans le diagnostic de panne, le délai de rétablissement du service est souvent critique. Dans les systèmes industriels complexes, il existe toujours un arbre parallèle basé sur le temps qui peut conduire à un arrêt total du système si le défaut n'est pas corrigé dans différentes limites de temps. Les allers-retours seraient plus susceptibles d'entraîner une défaillance totale, ce qui peut entraîner des opérations de restauration qui prennent beaucoup plus de temps (comme la vidange des réservoirs et des pipelines pour redémarrer une raffinerie).

C'est comme couper une branche d'arbre - pas besoin de retourner au tronc lorsque vous essayez de trouver une seule brindille.

Les ODD ont la propriété supplémentaire de fournir des conseils basés sur des probabilités ou des seuils afin d'aider à prendre des décisions lorsque l'arbre est traversé.

Voici un lien vers un bon livre sur le sujet, intitulé Fault Detection and Diagnosis in Industrial Systems (page 224), où il décrit les avantages du diagnostic basé sur les ODD:

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