Главная » Java, Структуры данных и алгоритмы » Направленные графы

0

В этом разделе обсуждаются вопросы, специфические для направленных графов, известных также как диграфы (digraph), все пути которых строго направлены.

Достижимость

Одним из основополагающих вопросов теории направленных графов является понятие достижимости, определяющее место, которого можно достичь в направленном графе. Обходы в направленном графе выполняются только в направлении, определяемом направлениями маршрутов, то есть направлениями прохождения всех путей в процессе обхода. Имея узлы и и v в диграфе G, говорим, что и достигает v (и v достижим для и), если имеет направленный путь от и к v. Можно также сказать, что узел v достигает пути (w,z), если v достигает узла происхождения w данного пути.

Диграф G является строго связанным, если для любых двух узлов и и v в нем и достигает v, a v достигает.и. Направленным циклом графа G является цикл, в котором все пути проходятся согласно определяемым ими направлениям (отметим, что G может иметь цикл, состоящий из двух путей, имеющих противоположное направление и соединяющих одну и ту же пару узлов). Диграф G является ацикличным при отсутствии в нем направленных циклов (см. рис. 12.8).

Транзитивным замыканием (transitive closure) диграфа б является диграф (?[26], содержащий такие же узлы, но всегда имеющий путь (u,v), если существует направленный путь от и до v. Это означает, что <5* определяется, основываясь на G и добавляя дополнительный путь (u,v) для каждого и и v таким образом, что v достижим из и (но до этого в G не существовало пути (u,v)).

Рис. 12.8. Примеры достижимости в диграфе: (а) направленный маршрут из BOS в LAX указан длинным пунктиром; (Ь) направленный цикл (ORD, MIA, DFW, LAX, ORD) указан длинным пунктиром; его узлы образуют строго связанный подграф; (с) подграф узлов и путей, достижимых из ORD, выделен коротким пунктиром; (d) удаление синих путей, обозначенных пунктиром, позволяет создать ацикличный диграф

В число интересных проблем, касающихся достижимости в диграфе G, входят следующие:

•  для узлов и и v определить достижимость v из и;

•  найти все узлы в (5, достижимые из указанного узла s\

•  определить, является ли G строго связанным;

•  определить, является ли G ацикличным;

•  вычислить транзитивное замыкание G* графа G.

Далее рассмотрим несколько алгоритмов решения этих задач.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии