АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Свести к задаче о раскраске следующую задачу и решить ее.

Лабораторная работа №7. Тема: «Задача о раскраске графа»

Примеры задач, для решения которых нужно найти хроматическое число и оптимальную раскраску графа.

Задача 1. Составление расписания. Нужно прочесть несколько лекций нескольким группам студентов. Некоторые из лекций не могут читаться одновременно, например, потому, что их читает один и тот же лектор, или их надо читать одной и той же группе студентов, или они должны проходить в одном и том же компьютерном классе. Требуется составить расписание так, чтобы чтение всех лекций заняло минимально возможное время (в качестве единицы времени в данной задаче естественно рассматривать одну пару). Переведем эту задачу на язык графов. Построим граф G, в котором вершины соответствуют лекциям и две различные вершины смежны тогда и только тогда, когда соответствующие лекции не могут читаться одновременно. Очевидно, что любая правильная раскраска графа G определяет допустимое расписание (если при этой раскраске использовано k цветов, то для всякого i = 1, 2,..., k вершины, раскрашенные i -м цветом, дают список лекций, которые надо читать на i -й паре). И наоборот, любое допустимое расписание определяет правильную раскраску графа G. Таким образом, составление оптимального расписания сводится к нахождению оптимальной раскраски построенного нами графа.

Пример задачи составления расписания. В студенческих группах КН-101 и КН-102 надо провести занятия по алгебре, дискретной математике, математическому анализу и истории (одно занятие по каждому предмету). Занятия по каждому предмету проводятся с каждой группой отдельно. Занятия по алгебре и по дискретной математике ведет преподаватель X, по математическому анализу − преподаватель Y, по истории − преподаватель Z. Найти минимальное число пар, в которые можно «уложить» все занятия, и составить соответствующее расписание.

Решение. Построим граф с вершинами А1, А2, Д1, Д2, М1, М2, И1 и И2 (буква соответствует предмету, а цифра − номеру группы). Соединим ребрами вершины, соответствующие парам, которые нельзя проводить одновременно. Получим граф, изображенный на следующем рисунке слева. Вершины А1, А2, Д1 и Д2 этого графа порождают в нем подграф, изоморфный графу K₄. Следовательно, хроматическое число нашего графа ³ 4. На следующем рисунке справа указана правильная раскраска нашего графа в 4 краски. Следовательно, хроматическое число графа равно 4, т. е. все занятия можно провести за 4 пары. Соответствующее расписание указано в таблице:

Задача 2. Распределение оборудования. Имеется некоторое количество работ и механизмов для их осуществления. Для выполнения всех работ требуется одинаковое время. При этом никакой из механизмов не может быть занят одновременно более чем в одной работе. Нужно распределить механизмы так, чтобы общее время выполнения работ было минимально возможным.

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

Пример задачи распределения оборудования. На предприятии планируется выполнить 8 работ: v1, v2,..., v8. Для выполнения этих работ необходимы механизмы a1, a2,..., a6. Использование механизмов для каждой из работ определяется следующей таблицей:

Ни один из механизмов не может быть использован одновременно на двух работах. Выполнение каждой работы занимает 1 час. Как распределить механизмы, чтобы суммарное время выполнения всех работ было минимальным и каково это время? Решение задачи дано на следующем рисунке.

Решение. Рассмотрим граф G, вершинами которого являются планируемые работы v1, v2,..., v8, а ребра соединяют работы, в которых участвует хотя бы один общий механизм (и которые, по этой причине, нельзя проводить одновременно). Этот граф изображен на следующем ривунке. Вершины v1, v2, v4, v5 порождают подграф графа G, изоморфный K₄. Следовательно, c(G)³ 4. Цифры в скобках на рисунке указывают правильную раскраску графа G в 4 краски. Следовательно, c(G) = 4. Таким образом, все работы можно выполнить за 4 часа. Для этого, в соответствии с найденной раскраской графа G, надо в 1-й час выполнять работы v1 и v6, во 2-й − работы v2 и v3, в 3-й − работы v4 и v8, в 4-й − работы v5 и v7.

Задание. 1. Решить 2 задачи (упражнения) из Андерсона:

Свести к задаче о раскраске следующую задачу и решить ее.

Задача 1 (для вариантов 1-10). Составить такое расписание экзаменов в конце семестра, чтобы ни одному студенту не пришлось сдавать более одного экзамена в день. При этом количество дней, в течение которых проводятся экзамены, должно быть минимальным. Каждый студент выбирает свой набор учебных курсов из п возможных (американская система).

Вариант 1.

Вариант 2.

Вариант 3.

Вариант 4.

Вариант 5.

Вариант 6.

Вариант 7.

Вариант 8.

Вариант 9.

Вариант 10.

Задача 2 ( для вар-тов 11-20). Предприятие выпускает детали n видов Д1, Д2, … Дn на станках k типов: C1, C2, …, Ck. Использование станков для каждого вида продукции задается таблицей из вашего варианта.

Выпуск каждой детали занимает 1 час. Как следует распределить станки, чтобы суммарное время выпуска всех деталей было минимальным? Каково это время?

Вариант 11.

Вариант 12.

Вариант 13.

Вариант 14.

Вариант 15.

Вариант 16.

Вариант 17.

Вариант 18.

Вариант 19.

Вариант 20.

Дата добавления: 2015-09-27 | Просмотры: 1839 | Нарушение авторских прав