Решение задачи компоновки конструктивных узлов
Рассмотрение преимуществ простого формального последовательного алгоритма разбиения графа на заданное число кусков, максимизирующего суммарное число внутренних ребер, входящих в выделенные куски. Построение матрицы смежности графа и ее преобразование.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 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