Алгоритмы решения задачи компоновки конструктивных узлов
Анализ алгоритма разбиения графа, приводящего к минимуму числа соединительных ребер за конечное число шагов при наличии ограничений. Методика определения количества внешних соединительных ребер составного элемента графа до внесения в него вершин.
| Рубрика | Математика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 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Примеры решения задач по заданию графов. Определение основных характеристик графа: диаметра, радиуса, эксцентриситета каждой вершины. Вычисление вершинного и реберного хроматического числа. Упорядоченность матричным способом и построение функции.
контрольная работа [224,6 K], добавлен 05.07.2014Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
презентация [36,1 K], добавлен 16.09.2013Алгоритм построения минимального остовного дерева. Последовательность выполнения алгоритма Прима, его содержание и назначение. Процедура рисования графа. Порядок составления и тестирования программы, ее интерфейс, реализация и правила эксплуатации.
курсовая работа [225,0 K], добавлен 30.04.2011Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы.
курсовая работа [951,4 K], добавлен 22.01.2014Число Пи как математическая константа. Основные особенности вычисления числа Пи. Методы определения численного значения числа Пи. Влияние трудов И. Ньютона и Г. Лейбница на ускорение вычисления приближенных значений Пи. Анализ формул древних ученных.
курсовая работа [1,8 M], добавлен 26.09.2012Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008Проверка справедливости тождеств или включений с использованием алгебры множеств и диаграмм Эйлера-Венна. Изображение графа и матрицы отношения, обладающего свойствами рефлексивности, транзитивности и антисиммеричности. Изучение неориентированного графа.
контрольная работа [1,3 M], добавлен 05.05.2013Загальні типи правильних опуклих многогранників. Властивості тетраедрів, кубів, октаедрів, додекаедрів та ікосаедрів. Кількість сторін, ребер та вершин многогранника. Формули для визначення площі поверхні многогранників. Винаходження декартових координат.
презентация [317,7 K], добавлен 12.12.2011Число как основное понятие математики. Натуральные числа. Простые числа Мерсенна, совершенные числа. Рациональные числа. Дробные числа. Дроби в Древнем Египте, Древнем Риме. Отрицательные числа. Комплексные, векторные, матричные, трансфинитные числа.
реферат [104,5 K], добавлен 12.03.2004Применение интервальных графов. Алгоритмы распознавания интервальных графов: поиск в ширину, поиск в ширину с дополнительной сортировкой, лексикографический поиск в ширину, алгоритм "трех махов". Программа задания единичного интервального графа.
курсовая работа [1,5 M], добавлен 10.02.2017
