Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

Часть III. Теория электрических цепей

14. Алгоритмы анализа графов

При исследовании отдельных практических задач появляются графы. Первым шагом в таких исследованиях было определение теоретико-графовых свойств рассматриваемой проблемы, которые помогли бы нам при определении метода ее решения. Так, в гл. 11— 13 мы установили несколько полезных теоретико-графовых свойств электрических цепей и на основе использования этих свойств разработали различные методы вывода уравнений цепи. При изучении транспортных сетей наибольший интерес представляет определение максимального потока. В качестве первого шага в этом направлении мы выделяем в разд. 15.7 несколько свойств этих сетей, которые приведут нас к теореме о максимальном потоке и минимальном разрезе. Эта теорема образует основу алгоритма расстановки меток Форда — Фалкерсона для нахождения максимального потока. Обычно решение задачи включает анализ графа или проверку его на наличие того или иного свойства. Графы, возникающие при изучении реальных практических задач, очень громоздки и сложны. Поэтому для эффективного анализа таких графов необходима разработка соответствующих вычислительных алгоритмов.

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

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

результаты по сложности будут относиться к анализу алгоритмов в худшем случае.

Существуют различные методы представления графа в вычислительной машине. Два из наиболее распространенных используют матрицу смежности (разд. 6.10) и список смежности. Представление графа матрицей смежности не очень эффективно в случае разреженных графов. При представлении графа списком смежности каждой вершине сопоставляется список, который содержит все ребра, инцидентные ей. Детальное обсуждение структур данных для представления графа может быть найдено в некоторых из ссылок, перечисленных в конце главы.

Существуют алгоритмы, которые трудны для построения, но доказательства корректности которых тривиальны. Другие алгоритмы легко представить, но доказательства их корректности весьма сложны. Более того, существуют непроанализированные тривиальные алгоритмы. Примеры таких алгоритмов имеются в разделах этой и следующей глав.

С целью последующего обсуждения разделим алгоритмы на две группы: алгоритмы анализа графов и алгоритмы решения задач оптимизации на графах. В этой главе мы исследуем алгоритмы первой группы. Вообще говоря, в этой главе обсуждаются алгоритмы, относящиеся к следующим основным темам:

1. Транзитивное замыкание.

2. Транзитивная ориентация.

3. Поиск в глубину.

4. Двусвязность и сильная связность.

5. Графы программ.

<< Предыдущий параграф Следующий параграф >>
Оглавление