Задача распределения сменных заданий рабочим участка механообработки

Задание:
Составить граф G соответствия выполняемых работ и производственного оборудования цеха.
Составить план распределения работ по единицам оборудования (совершенное или максимальное паросочетание).
Определить хроматическое число графа G (любым известным способом), дать интерпретацию этого числа для данной задачи
Определить пустой подграф максимальной мощности графа G. Объяснить полученный результат.

Порядок работы:
Составить бихроматический (двудольный) граф распределения работ между имеющимся оборудованием.
2. Построить на заданном двудольном графе совершенное паросочетание, если невозможно – максимальное по алгоритму с чередующимися цепями:
1) Выбрать пробное паросочетание П 1-1 по принципу: «1-й из множества А1 к 1-му не занятому из множества А2»;
2) Построить чередующуюся цепь из любой незанятой вершины i множества А1 в любую первую незанятую вершину из множества А2. При выборе фрагмента цепи из исходного паросочетания возможны фрагменты цепи типа «одна вршина - ко многим», что в дальнейшем влечет сочетание «многие – ко многим», поэтому возникает необходимость в уточнении путем построения обратной чередующейся цепи;
3) При достижении первой незанятой вершины j множества А2 -прямую чередующуюся цепь закончить и составить одну обратную, однозначную чередующуюся цепь из j в i ;
4) Увеличить паросочетание П до П1 за счет фрагментов из исходного распределения;
5) Если остались незанятые вершины - повторить с п.2, иначе – закончить.

3.Для определения хроматического числа воспользоваться алгоритмами:
стягивания вершин, расположенных на расстоянии 2 ребер друг от друга, до получения связного полного подграфа, число вершин которого – хроматическое число;
построения дерева всех полных подграфов (каждая ветвь от корня до концевой вершины – один полный подграф).
4. Для определения пустого подграфа максимальной мощности воспользоваться алгоритмом построения дерева всех пустых подграфов, каждая ветвь от корня до концевой вершины которого, один пустой подграф.

Исходные данные:
Данные приведены по вариантам. Элементы множества А1={a,b,c,d,e,f,g,h} соответствуют элементам множества А2={1,2,3,4,5,6,7,8}.
4
a 2 3 4
b 1
c 2 3
d 2 3
e 1 4 6 7
f 1 5 6
g 5 6
h 7 8

A1={█(■(a&b&■(c&d&■(e&f&■(g&h))))@■(2&1&■(2&2&■(1&1&■(5&7))))@■(■(3&&■(3&3&■(4&5&■(6&8))))@■(■(4&&■(&&■(6&6&■(&))))@■(&&■(&&■(7&&■(&)))))))┤
A2={1,2,3,4,5,6,7,├ 8}┤










Лабораторная работа № 6
«Определение оптимального маршрута обработки отверстий детали (по матрице достижимости на произвольном графе и методом «ветвей и границ» на полном связном графе)»
Задание
В детали необходимо высверлить 5 отверстий одинакового диаметра. Время на переналадку оборудования между операциями известно и зависит от местоположения отверстия. Определить порядок выполнения операций, при котором суммарное время на обработку всех отверстий окажется минимальным.
2 часть (удалить из исходного графа ребра, заданные константами, получим связный неполный граф)
Порядок выполнения:
1. Построить граф по матрице смежности
2. Составить матрицу достижимости. Определить по ней незамкнутые маршруты обхода вершин графа.
3. Вычислить минимальный маршрут.
4. Сформулировать признак определения в матрице достижимости (или матрицах с путями некоторой длины) искомых маршрутов.

ПРИМЕЧАНИЕ ко 2-й части. Ребра в матрицах обозначить не через коэффициенты, а через инцидентные им вершины. Например, ребро (или путь длины 1) между вершинами a и c – (ac). Далее, в матрицах смежности с путями длины два при вычислениях происходит присоединение к (ac) (cd). Средняя вершина является промежуточной и два смежных ребра (или путь длины 2) между вершинами ad обзначим как (acd).
j i a b c d e