Решение задачи компоновки.

Опишем схему графом

Опишем матрицу смежности

Выделяем первую запрещенную вершину

Составляем список вершин, смежных

, – запрещенная

Для вершин определяем относительные веса

– выбираем , т.к. она одна

Полученную вершину , помещаем в кусок

Подсчитываем число вершин в куске

Составляем список вершин, смежных

Для вершин определяем относительные веса

Выбираем вершину

Полученную вершину , помещаем в кусок

Подсчитываем число вершин в куске

, кусок сформирован.

Удаляем из матрицы строки и столбцы, соответствующие номерам вершин, вошедших в кусок .

 

Выделяем вторую запрещенную вершину

Составляем список вершин, смежных

Для вершин определяем относительные веса

Выбираем вершину

Полученную вершину , помещаем в кусок

Подсчитываем число вершин в куске

Составляем список вершин, смежных

, – запрещенная

Для вершин определяем относительные веса

Выбираем вершину

Полученную вершину , помещаем в кусок

Подсчитываем число вершин в куске

, кусок сформирован.

– т.к. остались последние вершины.

 

Инструкция пользователя

Программа написана на языке Delphi.

1) Для начала работы программы необходимо запустить файл “algoritm.exe”. В появившемся окне нажимаем кнопку «Ввод» около матрицы. Подсчитывается локальная степень вершин. Рис.1

Рис. 1

2) Нажимаем кнопку «Граф» открывается окно исходного графа. Рис.2

Рис. 2

3) Нажимаем вторую кнопу «Ввод», а затем «Компоновка фрагментов». Рис. 3

Рис. 3

4) Открывается окно с графом, разбитым на три куска, показанное на рис. 4

Рис. 4

5) Выход из программы осуществляется нажатием на «красный крестик» в правом верхнем углу окон.

 

Заключение

В ходе выполнения данной курсовой работы мною были изучены: задачи компоновки, алгоритмы компоновки.

Произведен ручной счет разбиения графа на кусков с учетом запрещенных вершин.

Разработана программа, разрезающая заданную схему соединения, представленную в виде графа и матрицей смежности, на 3 куска с учетом запрещенных вершин.

В результате была получена следующая компоновка: