Раскрашивание графа МакГрегора
В апрельском выпуске журнала Scientific American за 1975 год Мартин Гарднер в своей колонке «Математические игры» опубликовал список шести основных математических открытий 1974 года, о которых «по той или иной причине недостаточно сообщалось как научному сообществу, так и общественность в целом ». Одним из них был планарный граф со 110 узлами, приписываемый Уильяму МакГрегору из Ваппингерс-Фоллс, штат Нью-Йорк, который, по его утверждениям, нельзя раскрасить менее чем в 5 цветов, тем самым опровергая пока ещё не доказанное предположение о том, что 4 цветов достаточно для окраски любого планарнго графа. Это не понравилось многим читателям, так это месяц публикации номера. Подробнее об истории можно прочитать здесь .
Вот график, нарисованный в виде карты
Попытка закодировать возможную окраску этого графа как BDD практически неосуществима. Я предполагаю, что для этого потребуется более одного миллиарда узлов (поскольку минимальный разрез графа имеет ширину 20 узлов, и BDD потребуется экспоненциально кодировать почти все комбинации цветов для этих узлов).
Раскраска графика как задача SAT
С другой стороны, раскраска графа с помощью решателя логической выполнимости (SAT) вполне возможна. Решателю нужно найти только одно возможное решение, поэтому перед ним не стоит сложная задача кодирования всех возможных раскрасок. Вот цвет, созданный решателем ZChaff, работающим менее чем за одну секунду на портативном компьютере.
Посмотрите следующее видео на Youtube, показывающее, как продвигается этот поиск:
Также можно заставить решатель генерировать «сбалансированную» раскраску, потребовав от него найти решение, используя два цвета (зеленый и синий) 27 раз и два цвета (красный и желтый) 28 раз.
Решатели SAT также могут использоваться для решения задач оптимизации, выполняя серию вызовов решателей для выполнения двоичного поиска по целевой функции. Если мы попросим решающую программу найти раскраску, которая сначала минимизирует количество узлов, окрашенных в зеленый цвет, а затем минимизирует число, окрашенное в синий цвет, а затем в красный, мы получим раскраску всего из 7 зеленых узлов, 34 синих и красных и 35 желтых.
На основании дальнейших экспериментов можно констатировать, что до назначения цветов это решение обладает уникальными свойствами:
- Это единственная окраска, в которой один цвет используется не более 7 раз.
- Это единственная окраска, в которой один цвет используется не менее 35 раз.
______________________________________________________________________________________________________________
Последнее изменение: среда, 12 мая, 10:19:05 EDT 2010