оптимизационные задачи на графах

Заключение

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

Содержание

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1. Основные определения и понятия теории графов . . . . . . . 2
2. Оптимизационные задачи на графах . . . . . . . . . . . . . . 4
3. Алгоритм построения минимального остова . . . . . . . . . . 7
4. Реализация жадного алгоритма поиска минимального
остовного дерева на MatLab . . . . . . . . . . . . . . . . . . . 8
5. Тестирование работы программы поиска минимального
остовного дерева . . . . . . . . . . . . . . . . . . . . . . . . 12
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . .17
Список использованной литературы . . . . . . . . . . . . . 18

ВВЕДЕНИЕ

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