Мы читали об алгоритмах MST, сильной связности, маршрутизации и т. Д. В ориентированных графах.
Также недавно люди занимались исследованием динамических и отказоустойчивых алгоритмов для ориентированных графов.
Но мне было интересно, есть ли какие-нибудь практические приложения, где сеть подчеркивания графа «Направлена». За исключением социальных сетей, все проблемы, о которых я мог подумать, такие как железнодорожная / автомобильная сеть, сеть Интернет и т. Д., Касаются только неориентированных графиков.
Редактировать 1: Я понимаю, что они могут быть использованы для моделирования некоторых сценариев, куда направляются ссылки, но мне было интересно, как часто эти сценарии встречаются в реальном мире, и насколько важно изучение отказоустойчивости для ориентированных графов.
Ответы:
Напомним, что ориентированный граф - это граф, у которого ребра имеют связанное с ними направление.
Используя ориентированный граф, вы можете представлять асимметричные отношения между узлами, тогда как в неориентированном графе мы можем представлять только симметричные отношения.
Практически, используя ориентированный граф, вы можете представить:
Помимо этих классических примеров, вы можете изобразить множество других реальных сценариев (финансовая торговля, планирование, инфекционные заболевания, цитирование, контроль и т. Д.), Которые требуют упорядоченных отношений [1] .
источник
Ориентированные графы существуют. Как уже упоминалось в комментариях, ориентированные ациклические графы (DAG), в частности, чрезвычайно полезны во многих вычислительных задачах, таких как компиляция кода.
Кроме того, стоит отметить, что большинство алгоритмов направленного графа можно использовать в ненаправленном случае просто путем замены каждого ненаправленного ребра двумя направленными ребрами. Двойственная попытка сделать ориентированный граф из неориентированного графа невозможна для большинства алгоритмов.
источник
Начало топологической сортировки (фундаментальная операция над ориентированными ациклическими графами) лежит в сетях зависимостей в управлении проектами, в частности методе PERT . Кан и Лассер оба цитируют PERT в своих статьях и основывают на них свои примеры, например
Планирование работы онлайн все еще выполняется с сетью этого типа; например, система ETL планирует запуск заданий только после выполнения заданий, предоставляющих свои входные данные.
источник
Ответ: Из ОП я делаю вывод, что вопрос на самом деле связан с ЦУР (подписанные ориентированные графы). Итак, вот мой ответ, который обращается к основным ориентированным графам, а затем приводит к ЦУР.
Направленные графы широко используются при анализе дерева отказов в промышленных системах. Когда вы устраняете причины неисправности, вы следуете ориентированному графу для изучения других возможностей.
Направленные графы используются для предотвращения контрпродуктивного пересмотра узлов, которые были эффективно устранены. При диагностике неисправностей зачастую время на восстановление службы имеет решающее значение. В сложных промышленных системах всегда существует параллельное дерево, основанное на времени, которое может привести к полному отключению системы, если неисправность не устранена в течение различных временных ограничений. Переход назад и вперед с большей вероятностью приведет к полному отказу, который может привести к операциям восстановления, которые занимают гораздо больше времени (например, слив резервуаров и трубопроводов для перезапуска нефтеперерабатывающего завода).
Это похоже на обрезку ветки дерева - не нужно возвращаться к стволу, когда вы пытаетесь найти одну веточку.
ЦУР обладают дополнительным свойством давать указания, основанные на вероятностях или пороговых значениях, чтобы помочь принимать решения при обходе дерева.
Вот ссылка на хорошую книгу на эту тему под названием «Обнаружение неисправностей и диагностика в промышленных системах» (стр. 224), где описываются преимущества диагностики на основе ЦУР:
https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224
источник