Алгоритмы решения задачи компоновки конструктивных узлов
Анализ алгоритма разбиения графа, приводящего к минимуму числа соединительных ребер за конечное число шагов при наличии ограничений. Методика определения количества внешних соединительных ребер составного элемента графа до внесения в него вершин.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 12.06.2016 |
| Размер файла | 10,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Размещено на http://www.allbest.ru
Часто при разбиении ставится требование получения равных по числу вершин частей графа. Кроме того, как правило, некоторые вершины графа жестко закрепляются за определенными частями. Такие вершины называются запрещенными.
Пусть задан граф G=(E,U) и подмножество запрещенных элементов QE, |Q|=q. Требуется найти такое разбиение P(G) графа G на m одинаковых кусков G1,G2,…,Gm, чтобы суммарное число соединяющих ребер было минимальным.
Рассмотрим последовательный алгоритм разбиения графа, приводящий к минимуму числа соединительных ребер за конечное число шагов при наличии ограничений.
Основная идея метода заключается в следующем. Сначала по кускам графа распределяются запрещенные вершины. Формирование первого куска начинается с вершины eеQ, которую априорно считаем входящей во множество вершин E1 первого куска G1=(E1,U1).
Составление кусков будем вести по уровням. Вершина eе в куске G1 образует первый уровень и на этом уровне E1=eе.
Для определения вершин второго уровня, т.е. второй вершины, которую необходимо поместить в G1, строится множество вершин, смежных eе.
Обозначим множество, содержащее вершину eе, смежные ей вершины, и не содержащее других запрещенных вершин через Гeе.
Введем понятие относительного веса (еi) для любой вершины еi графа G:
(еi)=(ei)-rik, k=1,m, (1)
где rik, k=1,m - число ребер, соединяющих вершину ei с вершинами сформированного подмножества E1, m=|E1|.
Из приведенного выражения (1) следует, что для получения требуемого куска из множества Гeе необходимо выбрать вершину с минимальной величиной (еi*) (чем больше связей у вершины из Гeе с вершинами из G1, тем меньше разность в (1) и тем меньше величина (еi)):
(еi*) = min (еi), eiГeе (2)
где iI=(1,2,…,t), t=|Гeе|.
Вершина еi* является вершиной второго уровня. На втором уровне E1=eе,ei*.
Далее рассматривается множество ГeеUГei*, и для каждой вершины еkГeеUГei*, определяется относительный вес по (1). Выбрав вершину еk* с минимальным весом, получим E1=eе,ei*,еk*.
Указанный процесс продолжается до тех пор, пока множество вершин E1 не будет содержать n1 вершин. Полученный кусок G1 удаляется из графа G. Последующие куски формируются аналогично.
Если при формировании куска G1 графа G несколько рассматриваемых вершин имеют одинаковый относительный вес, то в кусок G помещается вершина, имеющая большую локальную степень. Покажем это.
Пусть для вершин ei,еjE графа G=(E,U) локальные степени (ei)>(ej). В рассматриваемом случае (еi)=(еj) , а по определению
(еi) = (ei) - rik,
(еj) = (ej) - rjk, k=1,m,
(ei) - rik=(ej) - rjk (3)
(ei) -(ej) =rik - rjk
Т.к. (ei)>(ej),
То:
rik>rjk, k=1,m (4)
Обозначим число внешних соединительных ребер куска Gi до внесения в него вершин еi и ej через zi. Тогда при внесении в кусок Gi вершины ei число внешних ребер станет:
граф соединительный минимум ребро
*(еi)= zi-rik+((ei)- rik)= (еi)+ zi-rik (5)
новое + старое число ребер:
zi-rik:
zi - было внешних выводов в Gi;
rik - соединились с новым элементом и стали внутренними;
(ei)- rik:
(ei)-было у ei внешних выводов;
rik - стали внутренними
А при внесении ej число внешних ребер станет:
*(еj)= zi-rjk+((ej)- rjk)=(еj)+ zi-rjk (6)
Учитывая выражение (4), из (6) следует
Вычитая из (5) выражение (6) и учитывая (4), получаем:
*(еi)- *(еj)=((еi)+ zi-rik)-( (еj)+ zi-rjk)<0 (7)
*(еi)<*(еj)
т.е. при внесении вершины ei число внешних соединительных ребер уменьшилось.
Размещено на Allbest.ru
Подобные документы
Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Метод Форда-Беллмана для нахождения расстояния от источника до всех вершин графа. Алгоритмы поиска расстояний и отыскания кратчайших путей в графах. Блочно-диагональный вид и матрица в исследовании системы булевых функций и самодвойственной функции.
курсовая работа [192,1 K], добавлен 10.10.2011Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Понятие "граф" и его матричное представление. Свойства матриц смежности и инцидентности. Свойства маршрутов, цепей и циклов. Задача нахождения центральных вершин графа, его метрические характеристики. Приложение теории графов в областях науки и техники.
курсовая работа [271,1 K], добавлен 09.05.2015Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014