Глава 19. Орграфы и ориентированные ациклические графы. Разумеется, любая программа способна обрабо­тать лишь крохотную часть возможных орграфов; в самом деле

Разумеется, любая программа способна обрабо­тать лишь крохотную часть возможных орграфов; в самом деле, эти числа настолько велики, что у нас есть все основания утверждать, что фактически ни один орграф не окажется в числе тех, которые бу­дут обработаны какой-либо заданной программой. В общем случае трудно описать свойства орграфов, с которыми приходится сталкиваться на практике, и это обстоятельство заставляет нас так разрабаты­вать алгоритмы, чтобы они могли принимать на вхо­де любой возможный орграф. С другой стороны, с такого рода ситуациями нам уже приходилось стал­киваться (например, ни одна из 1000! перестановок 1000 элементов никогда не была обработана ни од­ной из программ сортировки). С другой стороны, вас, возможно, неприятно поразит тот факт, что, например, даже если все электроны вселенной способны привести в действие суперкомпьютеры,

способные выполнять обработку 10¹⁰ графов за секунду в течение всей жизни вселенной, то эти суперкомпьютеры не просмотрят и 10^-100 процента орграфов, состоящих из 10 вер­шин (см. упражнение 19.9).

Это небольшое отступление, касающееся подсчета графов, возможно, выделяет не­сколько моментов, которым мы уделяем особое внимание, когда проводим анализ алго­ритмов, и показывает их непосредственное отношение к изучению орграфов. Должны ли мы разрабатывать алгоритмы так, чтобы они хорошо работали в худшем случае, когда вероятность обнаружить орграф для худшего случая настолько мала? Есть ли смысл вы­бирать алгоритмы на основании анализа обычных случаев или все это лежит в области мате­матической фантазии? Если нашей целью является получение программной реализации, ко­торая эффективно работает на орграфах, с которыми мы имеем дело на практике, мы непосредственно сталкиваемся с проблемой описания таких орграфов. Разработать матема­тические модели, достаточно точно описывающие орграфы, с которыми нам, возможно, при­дется иметь дело в приложениях, еще труднее, чем модели неориентированных графов.

В этой главе мы вновь обратимся, но уже в контексте орграфов, к поднабору фунда­ментальных задач обработки графов, которые уже рассматривались в главе 17. При этом мы исследуем несколько задач, специфичных только для орграфов. В частности, мы рас­смотрим алгоритм поиска в глубину и несколько его приложений, включая задачу обна­ружения циклов (cycle detection) (с целью определить, не является ли рассматриваемый орг­раф графом DAG); задачу топологической сортировки (topological sort) (для решения, например, задачи составления расписаний для только что описанных графов DAG), а так­же вычисление транзитивных замыканий (transitive closure) и сильных компонент (strong components) (которые решают фундаментальную задачу поиска ориентированной пути меж­ду двумя заданными вершинами). Как и в любых других областях обработки графов, эти алгоритмы занимают диапазон от тривиальных до исключительно хитроумных; они харак­теризуются сложными комбинаторными структурами орграфа и одновременно предостав­ляют нам возможность изучать эти структуры.

Часть 5. Алгоритмы на графах