Решение задачи компоновки конструктивных узлов
Рассмотрение преимуществ простого формального последовательного алгоритма разбиения графа на заданное число кусков, максимизирующего суммарное число внутренних ребер, входящих в выделенные куски. Построение матрицы смежности графа и ее преобразование.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 12.06.2016 |
| Размер файла | 220,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Решение задачи компоновки конструктивных узлов
Рассмотрим простой формальный последовательный алгоритм разбиения графа G=(E,U) на заданное число кусков G1,G2,…,Gl, максимизирующий число ребер, входящих в выделенные куски и оперирующий с матрицей смежности R графа G.
Пусть граф G=(E,U) задан своей матрицей смежности R=||rij||, i,jJ=(1,2,…,n). Рассмотрим алгоритм разбиения графа на l кусков G1,G2,…,Gl с заданным количеством вершин в кусках tp (p=1,l).
Рассмотрим строку ei матрицы R, соответствующую вершине с максимальной локальной степенью (ei) и выбираем в ней наибольший элемент rij, причем ij. Вершины ei и ej относим к подмножеству E1'E1. Переход к шагу 2.
Складываем поэлементно строки и столбцы ei и ej матрицы R. Переход к шагу 3.
В суммарной строке eij определяем максимальный элемент rij,k, ki, kj, вершину ek относим к множеству E1'. Если |E1'|=|E1|, то кусок сформирован. Переход к 4 . Если |E1'|<|E1|, то ij принимаем за i,а k за j, и переход к шагу 2.
Удаляем из графа G вершины подмножества E1 со всеми инцидентными им ребрами, т.е. вычеркиваем из матрицы строки и столбцы, соответствующие вершинам из подмножества E1. Полученную матрицу R' принимаем за R и переходим к 1 шагу.
Если в матрице R осталось ровно |El| строк и столбцов, то работа алгоритма закончена.
Пример алгоритма 3
Дан граф G=(E,U) (рис. 5.1).
Необходимо разбить этот граф на 3 куска G1=(E1,U1), G2=(E2,U2), G3=(E3,U3), содержащих по 3, 2 и 2 вершины соответственно.
Матрица смежности графа имеет вид
|
R = |
e1 |
e2 |
e3 |
e4 |
e5 |
e6 |
e7 |
|||
|
e1 |
0 |
4 |
1 |
0 |
2 |
0 |
1 |
(e1)=8 |
||
|
e2 |
4 |
0 |
3 |
1 |
1 |
0 |
0 |
(e2)=9 |
||
|
e3 |
1 |
3 |
0 |
5 |
0 |
0 |
1 |
(e3)=10 |
||
|
e4 |
0 |
1 |
5 |
0 |
0 |
0 |
0 |
(e4)=6 |
||
|
e5 |
2 |
1 |
0 |
0 |
0 |
5 |
2 |
(e5)=10 |
||
|
e6 |
0 |
0 |
0 |
0 |
5 |
0 |
6 |
(e6)=11 |
||
|
e7 |
1 |
0 |
1 |
0 |
2 |
6 |
0 |
(e7)=10 |
Реализация алгоритма:
Рассмотрим строку e6 матрицы R, соответствующую вершине с максимальной локальной степенью (e6)=11 и выбираем в ней наибольший элемент r67=6. Вершины e6 и e7 относим к подмножеству E1'=e6,e7.
Т.к. |E1'|<|E1|=3, то поэлементно суммируем строки e6 и e7. Матрица смежности примет вид:
|
R = |
e1 |
e2 |
e3 |
e4 |
e5 |
e67 |
|||
|
e1 |
0 |
4 |
1 |
0 |
2 |
1 |
r16+ r17 |
||
|
e2 |
4 |
0 |
3 |
1 |
1 |
0 |
r26+ r27 |
||
|
e3 |
1 |
3 |
0 |
5 |
0 |
1 |
r36+ r37 |
||
|
e4 |
0 |
1 |
5 |
0 |
0 |
0 |
r46+ r47 |
||
|
e5 |
2 |
1 |
0 |
0 |
0 |
7 |
r56+ r57 |
||
|
e67 |
1 |
0 |
1 |
0 |
7 |
0 |
диагон. эл-ты = 0 |
||
|
r61+ r71 |
r62+ r72 |
r63+ r73 |
r64+ r74 |
r65+ r75 |
В строке e67 выбираем наибольший элемент e67,5=7. Вершину e5 относим к подмножеству E1'=e6,e7,e5. Т.к. |E1'|=|E1|=3, то кусок G1 сформирован.
Удаляем из графа G вершины подмножества E1 со всеми инцидентными им ребрами, т.е. вычеркиваем из исходной матрицы строки и столбцы e6,e7,e5. Получаем матрицу
|
R' = |
e1 |
e2 |
e3 |
e4 |
|||
|
e1 |
0 |
4 |
1 |
0 |
(e1)=5 |
||
|
e2 |
4 |
0 |
3 |
1 |
(e2)=8 |
||
|
e3 |
1 |
3 |
0 |
5 |
(e3)=9 |
||
|
e4 |
0 |
1 |
5 |
0 |
(e4)=6 |
Рассмотрим строку e3 матрицы R', соответствующую вершине с максимальной локальной степенью (e3)=9 и выбираем в ней наибольший элемент r34=5. Вершины e3 и e4 относим к подмножеству E2'=e3,e4. Т.к. |E2'|=|E2|=2, то кусок G2 сформирован.
Оставшиеся вершины e1 и e1 относим к подмножеству E3'=e1,e2 и кусок G3 сформирован.
граф разбиение кусок смежность
Результат разбиения графа G приведен на рис. 5.2.
Суммарное число внутренних ребер равно для полученного разбиения 22, а число соединительных ребер К=11, коэффициент разбиения ?(G)=22/11.
Алгоритм имеет преимущества по сравнению с алгоритмом 2, если матрица смежности представляющего схему графа имеет мало нулевых элементов.
Размещено на Allbest.ru
...Подобные документы
Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма.
курсовая работа [8,1 M], добавлен 07.09.2012Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
курсовая работа [145,5 K], добавлен 27.01.2013История и термины теории графов. Описание алгоритма Дейкстры. Математическое решение проблемы определения кратчайшего расстояния от одной из вершин графа до всех остальных. Разработка программы на объектно-ориентированном языке программирования Delphi 7.
контрольная работа [646,9 K], добавлен 19.01.2016Этапы нахождения хроматического числа произвольного графа. Анализ примеров раскраски графа. Характеристика трудоемкости алгоритма раскраски вершин графа Мейниеля. Особенности графов, удовлетворяющих структуру графов Мейниеля, основные классы графов.
курсовая работа [1,1 M], добавлен 26.06.2012Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.
курсовая работа [525,6 K], добавлен 14.07.2012Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией.
курсовая работа [334,1 K], добавлен 20.01.2013Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа [493,3 K], добавлен 27.12.2008Создание программного обеспечения для реализации алгоритма, позволяющего находить кратчайшее расстояние от одной из вершин графа до всех остальных, при условии, что ребра графа не имеют отрицательного веса. Примеры выполнения алгоритма Дейкстра.
курсовая работа [1,1 M], добавлен 11.01.2015Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения.
курсовая работа [23,1 K], добавлен 24.05.2015Специфика построения и минимизации детерминированного автомата методом разбиения. Построение детерминированной сети Петри, моделирующей работу распознающего автомата. Особенности программной реализации праволинейной грамматики, построение ее графа.
курсовая работа [615,1 K], добавлен 19.06.2012Пример матрицы смежности для соответствующей сети. Функция распределения степеней узлов. Вариант матрицы смежности для взвешенной сети. Распределение степеней для случайных графов. Требования к интерфейсу. Алгоритм модели Баррат-Бартелэмью-Веспиньяни.
контрольная работа [1,4 M], добавлен 13.06.2012Информационное обеспечение, система автоматизированного управления. Классификаторы технико-экономической информации, унифицированные документы. Этапы проектирования информационного обеспечения. Анализ методов и матрицы смежности информационного графа.
реферат [19,0 K], добавлен 29.10.2010Использование NP-трудных в сильном смысле задачи. Обслуживание требований без задержек. Алгоритм построения бесконтурного графа. Псевдополиномиальные сведения задач. Последовательный анализ вариантов допустимого расписания ориентированного графа.
курсовая работа [783,7 K], добавлен 15.06.2009Вершина в заданном графе с различным количеством вершин. Результаты обработки графа программой MyProject.exe. Сопряжение модулей программы. Модуль вывода матрицы смежности. Тесты черного ящика. Комбинаторное покрытие условий тестами черного ящика.
курсовая работа [44,8 K], добавлен 13.10.2012Способ представления графа в информатике. Алгоритмы поиска элементарных циклов в глубину в неориентированных графах. Описание среды wxDev-C++, последовательность создания проекта. Руководство пользователю программы поиска и вывода на экран простых циклов.
курсовая работа [783,2 K], добавлен 18.02.2013Моделирование передвижения муравьев. Метод ветвей и границ, ближайшего соседа. Ограничения, накладываемые на агента в стандартной постановке задачи коммивояжера. Использование графа видимости в алгоритме муравья. Структура данных алгоритма муравья.
дипломная работа [1,7 M], добавлен 07.02.2013Общее понятие графа, его виды и сущность вершинного покрытия. Написание точного алгоритма решения задачи о надежности сети, нахождение минимального покрытия. Реализация данного алгоритма на языке TurboC++. Код программы, решающий поставленную задачу.
курсовая работа [1,3 M], добавлен 27.06.2014Двоичные деревья в теории информации. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Обоснование выбора, описание алгоритма и структур данных. Обоснование набора тестов. Построение оптимального кода. Сущность алгоритма Хаффмана.
курсовая работа [241,6 K], добавлен 17.10.2008Программа реализации генетического алгоритма, использование визуальной среды программирования. Руководство пользователя, листинг программы. Возможность ввода параметров: объем популяции, число поколений, коэффициент скрещивания и мутации, число городов.
курсовая работа [2,9 M], добавлен 20.08.2009Преобразование матрицы системы линейных алгебраических уравнений (СЛАУ) с помощью алгоритма Гаусса. Решение задачи методом простой итерации. Создание блок-схемы и текста программы для решения СЛАУ, реализованной на языке программирования Turbo Pascal.
курсовая работа [1,2 M], добавлен 15.06.2013
