Курсовая работа: Нахождение кратчайшей цепи между вершинами произвольного графа

РЕФЕРАТ
Отчёт 22 стр., 1 кн., 16 рис., 5 источн., 2 прил.
ГРАФ, НЕОРИЕНТИРОВАННЫЙ ГРАФ, МАТРИЦА
Цель работы: Необходимо разработать программное обеспечение, которое реализует алгоритм нахождение кратчайшей цепи между вершинами произвольного графа
Объектом исследования является анализ работоспособности и целесообразности данного метода.






















СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1. МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
2. АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ
4. ТЕСТИРОВАНИЕ
5. ИНСТРУКЦИЯ ПРОГРАММИСТУ
6. ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЮ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ А
ПРИЛОЖЕНИЕ Б

ВВЕДЕНИЕ

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

• МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

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


Рисунок 1 - Ориентированный граф
· неориентированные

Рисунок 2 - Неориентированный граф
В ориентированном графе ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами.
В неориентированном графе по каждому из ребер можно осуществлять переход в обоих направлениях.
Алгори́тм Де́йкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от