На этот раз штука довольно простая, и ориентированная, вероятно, больше на школьников и сочувствующих. Это планировалось в задачи на elements, но я не придумал, как это впихнуть в одну задачу. Не пропадать же добру (приложен pdf, где тот же текст, но рисунки на нужных местах).
Начнем с известной детской задачки на сообразительность.
Задача 1. Чтобы полностью прожарить одну котлету требуется 1 минута. На сковородке помещается только две котлеты. Как за минимальное время пожарить три котлеты?
Решите прежде чем читать дальше. В давней книге Литлвуда "Математическая смесь" по поводу вот этой самой задачи написано: "Это не дотягивает до математики". Так себе реклама. Литлвуд был не прав. О теории, окружающей эту задачу пойдет речь здесь.
Решение. Первый ответ, который хочется сказать - 2 минуты: вначале 1 минуту жарим две котлеты одновременно, потом еще 1 минуту третью. Но этот способ не оптимален. А оптимальный способ таков: первые полминуты жарим котлеты K1 и K2, следующие полминуты - K1 и K3, и наконец еще полминуты - K2 и K3. В итоге каждая котлета жарится в сумме минуту - сколько положено, зато на готовку мы затратили 1,5 минуты. Теперь поймем, почему нельзя уложиться меньше чем в 1,5 минуты. Это проверить несложно: общее количество котлето-минут равно 1+1+1. Поскольку в каждый момент времени можно жарить не больше двух котлет, то время жарки будет не меньше чем (1+1+1)/2=1,5 по принципу Дирихле.
Задача 2. На той же сковородке пожарить n котлет за наименьшее время.
Задача 3. На большой сковороде помещается не более k котлет. Пожарить n котлет за наименьшее время. Составьте расписание готовки.
Теперь оторвемся от котлет и рассмотрим другую жизненную ситуацию.
Задача 4. На биологической конференции планируются секции по следующим темам: анатомия (А), биофизика (Б), вирусология (В), генетика (Г) и дендрология (Д). Каждая секция длится 1 час. Некоторые участники конференции изъявили желание участвовать сразу в двух секциях, поэтому секции А и Б не могут проходить одновременно и, аналогично, Б и В, В и Г, Г и Д, Д и А. Составьте такое расписание секций, чтобы длительность конференции была наименьшей возможной, при условии что
Вариант а) секции проходят без перерывов;
Вариант б) в работе секции могут быть перерывы (например, секция может пройти 20 минут, потом сделать перерыв, и, возобновившись, идти еще 40 минут).
Решение. Рассмотрим граф, соответствующий нашей задаче: его вершины - это секции, а ребрами соединены те секции, которые запрещено проводить одновременно (рис. 1). В пункте (а) каждая секция длится ровно час, поэтому необходимо распределить, какие секции будут проходить в первый час, какие - во второй час, и так далее. Назовем такое распределение правильным расписанием типа (а).
рис.1
Допустим, что у нас уже есть правильное расписание типа (а). Покрасим все секции первого часа в цвет 1, все секции, проходящие во второй час - в цвет 2 и так далее (см. пример на рис. 2). Получим раскраску вершин графа, у которой все ребра имеют концы разных цветов (потому что соответствующие им секции нельзя проводить одновременно!). Такие раскраски называются правильными вершинными раскрасками, а наименьшее число цветов, задействованных в правильной раскраске называется хроматическим числом графа (обозначение Х(Г)). И наоборот: каждой раскраске соответствует правильное расписание типа (а). Значит, ответ к пункту (а) - хроматическое число Х(С5), которое равно 3 (докажите это).
рис.2
Ответ к пункту (б) изображен на рис. 3, общее время конференции равно 2,5 часа. Легко убедиться, что указанное расписание никак нельзя "уплотнить". По тем же соображениям, что и в задаче с котлетами, время 2,5 часа является минимальным.
рис.3
Математической моделью расписаний типа (б) служат дробные хроматические раскраски и дробные хроматические числа графов. В названии кроется тот факт, что рассматриваемые объекты (в нашем примере это секции) можно "дробить", то есть разбивать на части.
Определение. Дробной (n,k)-раскраской графа Г называется правило, сопоставляющее каждой вершине графа k-элементное подмножество n-элементного множества цветов таким образом, что подмножества, сопоставленные смежным вершинам графа не пересекаются. Весом раскраски называется отношение n/k. Обычные раскраски - это в точности (n,1)-раскраски графа.
Дробным хроматическим числом графа Г (обозначение Хr(Г)) называется минимум весов всех возможных (n,k)-раскрасок графа Г. Из определения ясно, что Хr(Г)≤Х(Г).
Задача 5. Докажите, что Хr(С5)=5/2.
Задача 6. (а) Пусть Cm - цикл на m вершинах. Найти Хr(Сm). (б) Посчитайте дробные хроматические числа всех известных вам графов (или хотя бы ваших любимых).
Задача 7**. Докажите, что дробное хроматическое число корректно определено, то есть минимум действительно достигается при некоторых значениях n и k.
Задача 8. Кликой графа Г называется множество попарно смежных вершин. Антикликой называется множество попарно несмежных вершин. Докажите, что Хr(Г)≥k и Хr(Г)≥В/a, где В - количество вершин графа, k - максимальный размер клики, a - максимальный размер антиклики.
Задача 9*. Придумайте граф Г, у которого Хr(Г) > k и Хr(Г) > В/a.
Вернемся к биологической конференции. Как видно, приведенное на рис.3 расписание удобно разбивается на получасовые интервалы. В первые полчаса (12:00-12:30) проходят секции А и В, в следующие (12:30-13:00) - А и Г, и так далее. Если мы первому получасу сопоставим цвет 1, второму - цвет 2, и далее аналогично, то получим (5,2)-раскраску графа С5. У этой раскраски минимальный возможный вес 5/2, согласно задаче 5. Видно, что пункт (б) задачи про конференцию непосредственно связан с дробными хроматическими раскрасками - знаменатель "2" в определении веса раскраски появился по той причине, что "элементарные интервалы" у нас на этот раз не часовые, а получасовые.
Напрашивается вывод, что задача про котлеты также моделируется математически при помощи дробных раскрасок. Это действительно так, но нам потребуется еще одно обобщение. В примере с конференцией у нас был запрет проводить некоторые пары секций одновременно - такие пары мы закодировали графически при помощи ребер графа. В задаче с котлетами запрет иного рода. Любые две котлеты можно жарить вместе, а вот три - уже нельзя. Объект, который описывает эту ситуацию, называется гиперграфом.
Определение. Гиперграф H - это пара (V,E), где V - конечное множество (называемое множеством вершин гиперграфа), а E - некоторый набор подмножеств множества V (эти подмножества называются гиперребрами). В дальнейшем будет предполагаться, что каждое гиперребро содержит как минимум два элемента.
Граф является частным случаем гиперграфа. В этом случае все гиперребра содержат ровно два элемента и являются обычными ребрами.
Определение. Дробной (n,k)-раскраской гиперграфа H называется правило, сопоставляющее каждой его вершине k-элементное подмножество n-элементного множества цветов таким образом, что подмножества цветов, соответствующие вершинам гиперребра, не содержат общего элемента (то есть не пересекаются в совокупности). Весом раскраски, как и раньше, называется отношение n/k, а дробным хроматическим числом гиперграфа - минимальный вес раскраски. Хроматическим числом гиперграфа называется минимальный вес (n,1)-раскрасок.
Задача с котлетами моделируется гиперграфом H3 на трех вершинах K1,K2,K3 с единственным гиперребром {K1,K2,K3} - это означает, что тройку котлет K1,K2,K3 нельзя жарить одновременно. Как и следовало ожидать, Хr(H3)=3/2, см. рис.4. Если прерывать процесс готовки одной котлеты запрещено, то ответ: Х(H3)=2, как мы уже поняли ранее.
рис.4
Задача 10. Опишите гиперграфы, моделирующие задачи 2 и 3.
Задача 11. Синдикат производит пять видов товаров: лампочки (Л), тумбочки (Т), вешалки (В), палочки (П) и колбочки (К). Требуется произвести каждого товара по одной партии, при этом на производство партии уходит неделя. Из-за технологических особенностей нельзя одновременно производить следующие тройки товаров: {Л,Т,В}, {Т,В,П}, {В,П,К}, {П,К,Л}, {К,Л,Т}. Какое наименьшее время потратит синдикат на производство 5 партий, если: (а) производство партии фиксированного товара нельзя приостанавливать; (б) производство партии можно приостанавливать?
Задача 12**. Докажите, что ответом в этих и подобных задачах всегда является хроматическое число в случае, если процессы нельзя прерывать; и дробное хроматическое число в случае, если процессы разрешается прерывать. На основании написанного выше может возникнуть ощущение, что это очевидно, но на самом деле в случае дробных хроматических чисел эта задача - не очень-то простая. Чтобы доказать, попробуйте сформулировать задачу поиска расписания по-другому, и написать программу, вычисляющую оптимальное расписание.
Задача 13. Гиперграфовым замыканием графа Г назовем гиперграф С(Г), гиперребра которого - все подмножества вершин Г, не являющиеся антикликами в Г. Докажите что , Хr(С(Г))=Хr(Г) и Х(С(Г))=Х(Г).
Задача 14. Предложите определение клики и антиклики в гиперграфе и обобщите задачу 8 на случай гиперграфов.
Задача 15. Прежде чем уйти с работы домой работнику Васе необходимо сделать 5 важных дел, каждое из которых занимает час времени: ответить на письма коллег (используется клавиатура, мышь и интернет), нарисовать логотип фирмы (используется мышь, процессор и видеокарта), послушать музыку (колонки, интернет и процессор), выполнить установку обновлений (интернет, процессор и видеокарта) и, наконец, пройти игрушку (клавиатура, колонки, видеокарта). Известно, что колонки, мышь и клавиатура могут выполнять в каждый момент времени лишь одну задачу, а интернет, процессор и видеокарта - не более двух задач. Вася, подобно Юлию Цезарю, многозадачен. Помогите Васе быстрее уйти домой и опишите гиперграф, моделирующий эту задачу.
Комментариев нет:
Отправить комментарий