Cтраница 4
Эта теорема показывает, что отыскание функции Гранди для симметрического графа без петель сводится к задаче о раскраске соответствующего неориентированного графа ( любой раскраске отвечает функция Гранди) и, обратно, любой функции Гранди отвечает некоторая раскраска графа. [46]
Хотя процедура неявного перебора, описанная в этом разделе, является примитивным древовидным поиском ( в котором не нужно вычислять никакие оценки для ограничения ветвлений), тем не менее она нисколько не хуже других известных методов раскраски графов. Так, например, для графа с 30 вершинами, содержащего приблизительно третью часть множества всех ребер полного 30-вершинного графа, нахождение оптимальной раскраски с помощью алгоритма неявного перебора требует около 30 с машинного времени на вычислительной машине 1ВМ ИЗО. [47]
Хотя процедура неявного перебора, описанная в этом разделе, является примитивным древовидным поиском ( в котором не нужно вычислять никакие оценки для ограничения ветвлений), тем не менее она нисколько не хуже других известных методов раскраски графов. Так, например, для графа с 30 вершинами, содержащего приблизительно третью часть множества всех ребер полного 30-вершинного графа, нахождение оптимальной раскраски с помощью алгоритма неявного перебора требует около 30 с машинного времени на вычислительной машине IBM ИЗО. [48]
Действительно, взяв минимальную раскраску графа G, в которой указанные вершины окрашены одной краской, и сохранив как эту краску на вершине графа G, получившейся после склеивания, так и краски на остальных вершинах, получаем раскраску графа G в % ( G) красок. [49]
Покажем, что можно так изменить окраску вершин цепи j т, тн ], не меняя окраски остальных вершин графа, что каждая вершина этой цепи, за исключением, быть может, вершины т, будет окрашена в один из цветов из Ns, и раскраска графа оста нется правильной. [50]
С другой ] стороны, в [133] показано, что существуют приближенные постановки ЛГР-полных [ задач ( более точно, Р - полных, если следовать обозначениям, принятым в [133]), которые также являются ЛГР-полными, а в [56] показано, что приближенная постановка задачи раскраски графа является в некотором смысле такой же трудной, как и сама задача раскраски графа. Таким образом, Сахни и Гонзалес [133] указывают 5что некоторые трудные комбинаторные задачи являются более трудными, чем другие. [51]
В этой главе, оставаясь на уровне рассмотрения абстрактных объектов, мы постараемся попять, как все эти объекты могут бЕлть построены: как найти компоненты связности информационного графа, как определить множества R ( что просто) и Т ( что существенно сложнее), как, наконец, найти наилучшую раскраску графа несовместимости. Для этих построений нам нужно найти систематические процедуры, которые могут быть положены в основу практического решения задачи экономии памяти, например, на ЭВМ с помощью алгольных программ. [52]