«Алгоритм нахождения стягивающего дерева методом поиска в глубину»

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

Тема исследования: Алгоритм нахождения стягивающего дерева методом поиска в глубину.

Объект исследования – ориентированные графы и деревья.

Предмет исследования – нахождение стягивающего дерева методом поиска в глубину.

Цель работы: Разработка программы на языке Turbo Pascal алгоритма нахождения стягивающего дерева методом поиска в глубину.

Для достижения этой цели были поставлены следующие задачи:

 обзор литературных данных по теме исследования дипломной работы;

 дать теоретическое обоснование алгоритма нахождения стягивающего дерева методом поиска в глубину;

 провести в ручную анализ графа и найти стягивающее дерево;

 составить программу для каждой задачи, реализующий алгоритм нахождения стягивающего дерева методом поиска в глубину;

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

Анализ алгоритмов обхода

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

Рассуждение справедливо и для обхода в глубину. В этом случае мы заходим вглубь графа пока не наткнемся на тупик. Посетим ли мы, возвращаясь, все остальные узлы? Может ли так получиться, что в какую-то из вершин графа мы не зайдем? При каждом попадании в тупик мы возвращаемся до первого узла, из которого есть проход к еще не посещенному узлу. Тогда мы следуем этим проходом и снова идем по графу в глубину. Встретив новый тупик, мы вновь возвращаемся назад, пока не наткнемся на первую вершину с еще не посещенным соседом. Чтобы одна из вершин графа осталась непосещенной, нужно, чтобы она не была соседней ни для одной из посещенных вершин. А это и означает, что граф несвязен вопреки наши предположениям. При обходе в глубину мы также должны посетить все узлы.

Что можно сказать про эффективность такого алгоритма? Будем предполагать, что основная часть всей работы приходится на посещение узла. Тогда расходы на проверку того, посещали ли мы уже данный узел, и на переход по ребру можно не учитывать. Поэтому порядок сложности алгоритма определяется числом посещений узлов. Как мы уже говорили, каждая вершина посещается в точности один раз, поэтому на графе с N вершинами происходит N посещений. Таким образом, сложность алгоритма равна O(N)

Названный алгоритм может найти свои применения в программах для транспортных и коммуникационных сетей, таких как: железнодорожной транспортной сети, где вершины – станции, связи – дороги, таксомоторная сеть: вершины – места стоянки автомобилей, связи – пути подъезда; перемещение потока вещества по системе труб в определенный пункт назначения и т.д. На основе алгоритма поиска в глубину в графе можно построить программу вывода дерева наименьшей стоимости, что позволит рассчитывать кратчайшие пути к определенному месту назначения (вершине).

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

9. Кофман А. Введение в прикладную комбинаторику.-М.:Наука,1975.

10. Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978.

11. Кузнецов О.П. Дискретная математика для инженера, 3-е изд., перераб. и доп. – СПб: Издательство «Лань», 2004.

12. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.

13. Липский В. Комбинаторика для программистов.-М.:Мир, 1988.

14. Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир,1981.

15. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях.-Новосибирск: Наука; Сиб. отд-ние, 1990.

16. Окулов С.М.Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. - Киров, 1996.

17. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир,1985.

18. Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977, 352 с.

19. Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.:Мир,1984.

20. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992, 32 с.

21. Филипс Д., Гарсиа-Диас А. Методы анализа сетей. - М.: Мир, 1984.

22. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях.-М.:Мир,1963.

23. Фрэнк Г., Фриш И. Сети, связь и потоки.-М.:Связь,1978.

24. Харари Ф. Теория графов.-М.:Мир,1973.

25. Ху Т. Целочисленное программирование и потоки в сетях.- М.:Мир,1974.