Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 19. Орграфы и ориентированные ациклические графы. Разумеется, любая программа способна обработать лишь крохотную часть возможных орграфов; в самом деле
|
|
|
| РИСУНОК 19.2. ПОДСЧЕТ ЧИСЛА ГРАФОВ В то время как число различных неориентированных графов с V вершинами велико, даже когда V мало, число различных орграфов с V вершинами намного больше. Что касается неориентированных графов, то их число определяется формулой 2V(V+1)/2, в то время как число орграфов определяется формулой 2 |
Разумеется, любая программа способна обработать лишь крохотную часть возможных орграфов; в самом деле, эти числа настолько велики, что у нас есть все основания утверждать, что фактически ни один орграф не окажется в числе тех, которые будут обработаны какой-либо заданной программой. В общем случае трудно описать свойства орграфов, с которыми приходится сталкиваться на практике, и это обстоятельство заставляет нас так разрабатывать алгоритмы, чтобы они могли принимать на входе любой возможный орграф. С другой стороны, с такого рода ситуациями нам уже приходилось сталкиваться (например, ни одна из 1000! перестановок 1000 элементов никогда не была обработана ни одной из программ сортировки). С другой стороны, вас, возможно, неприятно поразит тот факт, что, например, даже если все электроны вселенной способны привести в действие суперкомпьютеры,
способные выполнять обработку 1010 графов за секунду в течение всей жизни вселенной, то эти суперкомпьютеры не просмотрят и 10-100 процента орграфов, состоящих из 10 вершин (см. упражнение 19.9).
Это небольшое отступление, касающееся подсчета графов, возможно, выделяет несколько моментов, которым мы уделяем особое внимание, когда проводим анализ алгоритмов, и показывает их непосредственное отношение к изучению орграфов. Должны ли мы разрабатывать алгоритмы так, чтобы они хорошо работали в худшем случае, когда вероятность обнаружить орграф для худшего случая настолько мала? Есть ли смысл выбирать алгоритмы на основании анализа обычных случаев или все это лежит в области математической фантазии? Если нашей целью является получение программной реализации, которая эффективно работает на орграфах, с которыми мы имеем дело на практике, мы непосредственно сталкиваемся с проблемой описания таких орграфов. Разработать математические модели, достаточно точно описывающие орграфы, с которыми нам, возможно, придется иметь дело в приложениях, еще труднее, чем модели неориентированных графов.
В этой главе мы вновь обратимся, но уже в контексте орграфов, к поднабору фундаментальных задач обработки графов, которые уже рассматривались в главе 17. При этом мы исследуем несколько задач, специфичных только для орграфов. В частности, мы рассмотрим алгоритм поиска в глубину и несколько его приложений, включая задачу обнаружения циклов (cycle detection) (с целью определить, не является ли рассматриваемый орграф графом DAG); задачу топологической сортировки (topological sort) (для решения, например, задачи составления расписаний для только что описанных графов DAG), а также вычисление транзитивных замыканий (transitive closure) и сильных компонент (strong components) (которые решают фундаментальную задачу поиска ориентированной пути между двумя заданными вершинами). Как и в любых других областях обработки графов, эти алгоритмы занимают диапазон от тривиальных до исключительно хитроумных; они характеризуются сложными комбинаторными структурами орграфа и одновременно предоставляют нам возможность изучать эти структуры.
Часть 5. Алгоритмы на графах
Упражнения
• 19.1. Назовите пример крупного орграфа, возможно, графа, описывающего управле
ние какими-либо объектами в оперативном режиме, — что-то наподобие графа биз
нес-операций одной из систем, работающей в оперативном режиме, или орграфа, оп
ределяемого связями Web-страниц.
• 19.2. Назовите пример крупного графа DAG, описывающего какую-нибудь деятель
ность, выполняемую в интерактивном режиме, возможно, графа, определяемого за
висимостями, связывающими определения функций в крупной системе программно
го обеспечения, или связями каталогов в крупной файловой системе.
19.3. Постройте таблицу, аналогичную представленной на рис. 19.2, не учитывая при
этом все орграфы и петли.
19.4. Каково число орграфов, содержащих V вершин и Е ребер?
о 19.5. Сколько орграфов соответствует каждому неориентированному графу, содержащему V вершин и Е ребер?
> 19.6. Сколько нужно числовых разрядов, чтобы выразить число орграфов, содержащих V вершин и E ребер, в виде 10-значного числа?
о 19.7. Начертите неизоморфные орграфы, содержащие три вершины.
•••19.8. Укажите число различных орграфов, содержащих V вершин и Е ребер, если мы считаем орграфы различными только тогда, когда они не изоморфны.
о 19.9. Вычислите верхнюю границу процентного отношения орграфов, содержащих 10 вершин, которые когда-либо могут быть просмотрены каким-либо компьютером в условиях предположений, сделанных в тексте, и с учетом того обстоятельства, что во вселенной имеется 1080 электронов и что срок существования вселенной не превысит 1020 лет.