Original:http://www.cs.cmu.edu/~bryant/boolean/macgregor.html

Раскраски графа Мак-Грегора

Вот некоторые переводы этой страницы на другие языки: В апреле в выпуске за 1975 год в Scientific American, Мартин Гарднер, в своей колонке «математические игры» опубликовал список того, что как он утверждал, было 6 основными математическими открытиями за 1974 год, что «по той или иной причине недостаточно сообщалось научному сообществу и широкой общественности.» Один был Вселенский, 110-узел графа, приписываемый Уильяму Мак-Грегору и Wappingers Фолсу,из Нью-Йорка, что как он утверждал не может быть окрашеным менее чем в 5 цветов, опровергая тем самым пока недоказанную гипотезу, что достаточно, чтобы цвет любого планарного графа имел 4 цвета. То, что многие читатели не оценили через месяц опубликования этого вопроса. Подробнее об истории можно найти здесь.

Вот график, как карта

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

Граф, раскраски как SAT проблема

С другой стороны, раскраски графа с Boolean выполнимостью решения (SAT) вполне является осуществимым. Для поиска только нужно найти одно из возможных решений, и поэтому он не сталкивается с сложнейшей задачей кодирования всех возможных расцветок. Вот окраска, порожденную ZChaff решателем котораяя работает около одной секунды на переносном компьютере

Проверьте следующие видео c Youtube, где показан как этот поиск продолжается:

Это также дает возможность заставить решатель создавать «сбалансированные» раскраски, требуя найти решение, с использованием двух цветов (зеленый и синий) 27 раз и два цвета (красный и желтый) 28 раз.

SAT решателей также может использоваться для решения задач оптимизации, выполнив серию вызовов решателей - сделать бинарный поиск по целевой функции. Если мы просим решатель найти окраску, что сначала минимизирует количество узлов выделеных зеленым цветом, а затем минимизируем число цветных синих линий, а затем красных линий,то мы получаем окраску с всего 7-ю зелеными узлами, 34 синими и красными узлами где 35 из них желтые узлы.

На основе дальнейших экспериментов, мы можем констатировать, что до назначения цветов, это решение обладает уникальными свойствами:


Randal E. Bryant
Последнее изменение: Wed, 12 мая 10:19:05 EDT 2010