Сюда я раз в 10 лет наваливаю задачек, которые постил в разное время вконтакте под тегом #вотэтазадача Решения, где есть, написаны в комментариях.
вотэтазадача 32. Геометрическая оптимизация в квадрате.
В квадрате 1х1 выбрали 7 фигур Ф1, Ф2,...,Ф7, так что Ф1 не пересекается с Ф2, Ф2 не пересекается с Ф3, Ф3 - с Ф4, ..., Ф7 не пересекается с Ф1. Какое наибольшее значение может принимать сумма площадей этих фигур?
Очевидное обобщение: есть произвольный граф G и каждой вершине графа сопоставляется фигура (например, в единичном квадрате) таким образом, что фигуры, сопоставленные смежным вершинам, не пересекаются. Получается нечто типа раскраски и условия правильности. Вопрос: какова наибольшая суммарная площадь всех фигур? Это аналог хроматического числа. Утверждается, что эта суммарная площадь равна максимальной мощности антиклики в графе (антиклика --- по определению, множество попарно несмежных вершин). Назовем это число N. Доказательство: рассмотрим произвольную точку в квадрате. Вершины, для которых соответстующие фигуры содержат заданную точку, образуют по условию антиклику, а значит эта точка содержится не более чем в N фигурах. Теперь "просуммируем" все такие неравенства по всем точкам (т.е. возьмем интеграл Лебега). Получим, что сумма площадей фигур </= N х площадь квадрата. Очевидно, что оценка достигается (надо взять максимальную антиклику и в ее вершины поставить весь квадрат, а в остальные вершины --- пустое множество). Доказано. В нашем случае граф --- цикл длины 7, для него максимальная антиклика состоит из 3 элементов.
Интересно, что аналогия с хроматическими инвариантами графа здесь не случайна. Например, если наложить условие, что площади всех фигур на вершинах равны, то получится более содержательный инвариант --- дробное хроматическое число (хотя это еще надо доказать, и в этом я не до конца уверен --- определение дробного хроматического числа другое). Если взять вместо квадрата и фигур в нем --- отрезок и его измеримые подмножества, то должно получится то же самое, при этом возникнет модель сложного производства с возможностью остановки. У вас есть несколько производимых товаров, при этом некоторые товары нельзя производить одновременно (получаем граф несовместимости). Каждому товару мы пытаемся сопоставить расписание (т.е. в каких интервалах на временной шкале он производится) таким образом, чтобы расписания несовместимых товаров не пересекались. При этом мы стараемся выпустить как можно больше товара. Если бы других ограничений не было, то все определялось бы максимальной антикликой, как описано выше. Однако от нас часто требуют выпустить заданное количество каждого товара, поэтому возникают дополнительные ограничения и все сводится к задаче линейного программирования. В самом тривиальном случае эта задача дает дробно-хроматическое число графа.
Это все очень клевые и интересные вещи. Желающие могут поиграться, подставляя вместо отрезка или квадрата другие пространства с мерой, например дискретные. Должны тоже получаться красивые модели с красивой математикой. Тема необъятная.
Очевидное обобщение: есть произвольный граф G и каждой вершине графа сопоставляется фигура (например, в единичном квадрате) таким образом, что фигуры, сопоставленные смежным вершинам, не пересекаются. Получается нечто типа раскраски и условия правильности. Вопрос: какова наибольшая суммарная площадь всех фигур? Это аналог хроматического числа. Утверждается, что эта суммарная площадь равна максимальной мощности антиклики в графе (антиклика --- по определению, множество попарно несмежных вершин). Назовем это число N. Доказательство: рассмотрим произвольную точку в квадрате. Вершины, для которых соответстующие фигуры содержат заданную точку, образуют по условию антиклику, а значит эта точка содержится не более чем в N фигурах. Теперь "просуммируем" все такие неравенства по всем точкам (т.е. возьмем интеграл Лебега). Получим, что сумма площадей фигур </= N х площадь квадрата. Очевидно, что оценка достигается (надо взять максимальную антиклику и в ее вершины поставить весь квадрат, а в остальные вершины --- пустое множество). Доказано. В нашем случае граф --- цикл длины 7, для него максимальная антиклика состоит из 3 элементов.
ОтветитьУдалитьИнтересно, что аналогия с хроматическими инвариантами графа здесь не случайна. Например, если наложить условие, что площади всех фигур на вершинах равны, то получится более содержательный инвариант --- дробное хроматическое число (хотя это еще надо доказать, и в этом я не до конца уверен --- определение дробного хроматического числа другое). Если взять вместо квадрата и фигур в нем --- отрезок и его измеримые подмножества, то должно получится то же самое, при этом возникнет модель сложного производства с возможностью остановки. У вас есть несколько производимых товаров, при этом некоторые товары нельзя производить одновременно (получаем граф несовместимости). Каждому товару мы пытаемся сопоставить расписание (т.е. в каких интервалах на временной шкале он производится) таким образом, чтобы расписания несовместимых товаров не пересекались. При этом мы стараемся выпустить как можно больше товара. Если бы других ограничений не было, то все определялось бы максимальной антикликой, как описано выше. Однако от нас часто требуют выпустить заданное количество каждого товара, поэтому возникают дополнительные ограничения и все сводится к задаче линейного программирования. В самом тривиальном случае эта задача дает дробно-хроматическое число графа.
Это все очень клевые и интересные вещи. Желающие могут поиграться, подставляя вместо отрезка или квадрата другие пространства с мерой, например дискретные. Должны тоже получаться красивые модели с красивой математикой. Тема необъятная.