Работа выполнена на отлично,автор выполнил в срок.Заказываю у этого автора не в первый раз,все быстро и качественно.Рекомендую
Информация о работе
Подробнее о работе
оптимизационные задачи на графах
- 17 страниц
- 2014 год
- 156 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
ВВЕДЕНИЕ
Граф представляет собой отображение отношений внутри некоторого множества объектов, представляемых вершинами графа: наличие или отсутствие связей между ними (в первом случае они соединены друг с другом ребрами; во втором случае ребра отсутствуют), а также количественно выраженная направленность и интенсивность связей.
Универсальность такого представления структуры позволяет описывать и давать количественную оценку широкого класса задач в технических, технологических, экономических и многих других приложениях.
Например, в виде графа отображают последовательность выполняемых работ при строительстве объектов, начиная от изыскательских работ и заканчивая обустройством прилегающих территорий, маршруты транспортировок материалов, взаимосвязи этапов работ, потоки ресурсов различного рода (материальных, финансовых, трудовых, энергетических), системы учета и управления проектами в соответствии с каждым из этапов и т.д.
Несмотря на различную природу описываемых отношений, графы обладают многими общими свойствами, что позволяет использовать методы дискретной математики и, в частности, теории графов для количественного описания их общих свойств, независимо от реальных объектов, которые они представляют.
Графы используют во всех областях науки и техники, в частности при принятии решении и в задачах оптимизации, когда в пространстве всех возможных состояний системы необходимо выбрать наилучшее с позиций поставленных цели и критериев.
Содержание
ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1. Основные определения и понятия теории графов . . . . . . . 2
2. Оптимизационные задачи на графах . . . . . . . . . . . . . . 4
3. Алгоритм построения минимального остова . . . . . . . . . . 7
4. Реализация жадного алгоритма поиска минимального
остовного дерева на MatLab . . . . . . . . . . . . . . . . . . . 8
5. Тестирование работы программы поиска минимального
остовного дерева . . . . . . . . . . . . . . . . . . . . . . . . 12
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Список использованной литературы . . . . . . . . . . . . . 18
Заключение
Проблема построения минимального остовного дерева достаточно разносторонняя, известна давно и продолжает исследоваться и сегодня. В настоящей работе представлен только базовый алгоритм.
Задача построения минимального остовного дерева встречается в различных областях. Интересным ее применением является проблема построения смешанного остовного дерева: построить для графа дерево со свойствами минимального остовного дерева и дерева кратчайших путей. Другой важной задачей является быстрое обновление минимального остовного дерева при изменении графа.
Здесь стоит отметить, что задача о минимальном остовном дереве является упрощением реальности. В самом деле, если соединяемые объекты находятся в вершинах единичного квадрата, разрешается соединять любые его вершины, и стоимость строительства пропорциональна его длине, то минимальное покрывающее дерево будет состоять из трех сторон квадрата. Между тем все его четыре вершины можно соединить двумя пересекающимися диагоналями, суммарная длина которых будет равна 22, что меньше 3 в первом случае.
Список использованной литературы
1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с.
2. Мартынов Н.Н. Matlab 7. Элементарное введение. М: "Кудиц-Образ", 2005г, 416 стр. EAN: 9785957900481
3. Потемкин В. Вычисления в среде MATLAB. Диалог-МИФИ. 2004.
4. Потемкин В. Система MATLAB. Справочное пособие. Диалог-МИФИ, 1997.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
