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

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

Ввод исходных данных: матрица с координатами вершин и матрица с ребрами и их весами: clear all disp('Решение задачи о минимальном покрытии') V=[0 4;1 4;2 4;3 4;4 4;0 3;1 3;2 3;3 3;4 3;... 0 2;1 2;2 2;3 2;4 2;0 1;1 1;2 1;3 1;4 1;... 0 0;1 0;2 0;3 0;4 0]; E=[1 2 1;3 2 2;4 3 3;5 4 4;6 1 5;2 7 6;8 2 7;3 8 8;... 9 4 9;9 5 8;10 5 7;7 6 6;8 7 5;8 9 4;10 9 3;11 6 2;... 7 12 1;13 8 2;14 9 3;15 10 4;12 11 5;13 12 6;13 14 7;... 14 13 8;5 5 10;15 14 9;16 11 8;12 17 7;13 18 6;... 20 15 5;17 16 4;17 18 3;18 17 2;19 18 1;19 20 2;... 5 5 8; 21 16 3;17 22 4;18 22 5;22 18 6;18 23 7;... 19 24 8;20 25 9;21 22 8;22 21 7;23 24 6;10 10 8;... 24 23 5;24 25 4]; grPlot(V,E); % начальный граф title('\bfНачальный граф со взвешенными ребрами') На рис. 5 показан скриншот для исходного графа, полученный после описанных шагов программы . Рис. 5 Исходный граф со взвешенными ребрами Сначала для сравнения решим невзвешенную задачу. В этом случае процедура строит первое встретившееся остовное дерево. nMST=grMinSpanTree(E(:,1:2)); % покрывающее дерево fprintf('Количество ребер в покрывающем дереве = %d\n',length(nMST)); fprintf('Общий вес = %d\n',sum(E(nMST,3))); grPlot(V,E(nMST,:)); % покрывающее дерево title('\bfПокрывающее дерево') На рис. 6 представлен скриншот для остовного, но не минимального дерева, в котором количество ребер 24 и их общий вес 114. Теперь получим минимальное остовное дерево и сравним результаты: количество ребер в минимальном остовном дереве = 24; общий вес = 81. nMST=grMinSpanTree(E); % минимальное покрывающее дерево fprintf('Количество ребер в минимальном покрывающем дереве = %d\n',... length(nMST)); fprintf('Общий вес = %d\n',sum(E(nMST,3))); grPlot(V,E(nMST,:)); % минимальное покрывающее дерево title('\bfМинимальное покрывающее дерево') На рис. 7 представлен скриншот для минимального остовного дерева, в котором количество ребер 24 и их общий вес 81. Таким образом, разработанная программа позволяет решить задачу о минимальном остовном дереве.  Количество ребер в покрывающем дереве = 24 Общий вес = 114 Рис. 6. Скриншот работы программы при получении остовного, но не минимального дерева  Количество ребер в минимальном покрывающем дереве = 24 Общий вес = 81 Рис. 7. Скриншот работы программы при получении минимального остовного дереваЗаключение Проблема построения минимального остовного дерева достаточно разносторонняя, известна давно и продолжает исследоваться и сегодня. В настоящей работе представлен только базовый алгоритм. Задача построения минимального остовного дерева встречается в различных областях. Интересным ее применением является проблема построения смешанного остовного дерева: построить для графа дерево со свойствами минимального остовного дерева и дерева кратчайших путей. Другой важной задачей является быстрое обновление минимального остовного дерева при изменении графа. Здесь стоит отметить, что задача о минимальном остовном дереве является упрощением реальности. В самом деле, если соединяемые объекты находятся в вершинах единичного квадрата, разрешается соединять любые его вершины, и стоимость строительства пропорциональна его длине, то минимальное покрывающее дерево будет состоять из трех сторон квадрата. Между тем все его четыре вершины можно соединить двумя пересекающимися диагоналями, суммарная длина которых будет равна 2√2, что меньше 3 в первом случае. Список использованной литературы 1. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е изд. — М.: Вильямс, 2005. — 1296 с. 2. Мартынов Н.Н. Matlab 7. Элементарное введение. М: "Кудиц-Образ", 2005г, 416 стр. EAN: 9785957900481 3. Потемкин В. Вычисления в среде MATLAB. Диалог-МИФИ. 2004. 4. Потемкин В. Система MATLAB. Справочное пособие. Диалог-МИФИ, 1997. Содержание ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Основные определения и понятия теории графов . . . . . . . 2 Оптимизационные задачи на графах . . . . . . . . . . . . . . 4 Алгоритм построения минимального остова . . . . . . . . . . 7 Реализация жадного алгоритма поиска минимального остовного дерева на MatLab . . . . . . . . . . . . . . . . . . . 8 Тестирование работы программы поиска минимального остовного дерева . . . . . . . . . . . . . . . . . . . . . . . . 12 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Список использованной литературы . . . . . . . . . . . . . 18 18 V4 V3 V1 V2 V1 V1 V1 V1 V1 V4 V1 V1 V3 V2 V3 V4 V3 V1 V4