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