Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
1. Теоретическая часть 1.1 Основные понятия теории графов 1.2 Связность графов 1.3 Задача о кратчайшей цепи 1.4 Метод Дейкстры нахождения кратчайшей цепи в связном графе 2. Реализация метода 2.1 Программная реализация метода Дейкстры 2.2 Описание логики программного модуля 2.3 Примеры работы программы Заключение Список использованных источников Приложение 1: Текст программы Приложение 2: графы тестовых расчетов Введение История человечества насчитывает много миллионов лет. Метод Дейкстры нахождения кратчайшей цепи в связанном графе является, пожалуй, самым удачным из методов минимизации, применение которых обеспечивает отыскание таковой цепи в графе. 1. Говорят, что задан конечный неориентированный граф, если заданы следующие два объекта [1]: 1) конечное множество , элементы этого множества называются вершинами графа; 2) Некоторое множество неупорядоченных пар элементов из , это множество обозначается , его элементы, то есть пары вершин, называются ребрами. метод дейкстра связный граф Тот факт, что граф определяется парой множеств и , записывается в виде .
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
