alt text

задан 31 Янв '15 14:50

изменен 31 Янв '15 18:34

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
1

Раскрашиваемость графа в два цвета равносильная отсутствию в нём циклов нечётной длины; эти циклы можно считать простыми.

Если $%A$% -- матрица смежности графа (фактически, это и есть заданная в условии функция $%f$%), то степени этой матрицы несут информацию о количестве путей заданной длины из каждой вершины в каждую (это известный теоретический факт). Рассматривая степени матрицы $%A$% с нечётными показателями, то есть $%A$%, $%A^3$%, $%A^5$%, ... (показатели можно брать не больше $%n$% ввиду анализа только простых циклов), мы должны прийти к тому, что все диагональные элементы этих матриц обязаны быть нулевыми.

Количество рассматриваемых матриц равно $%O(n)$%. Перемножение матриц, производимое по обычным формулам из линейной алгебры, требует полиномиального числа операций. Составляя схемы для всех упомянутых выше матриц и вычленяя из них информацию о диагональных элементах, мы получаем $%O(n^2)$% булевых переменных, для которых далее рассматривается схема-дизъюнкция. К ней надо добавить отрицание, чтобы получилась 1 на выходе в случае 2-раскрашиваемости графа. Общий размер такой схемы, очевидно, будет полиномиальным.

ссылка

отвечен 1 Фев '15 0:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,771
×131
×87

задан
31 Янв '15 14:50

показан
443 раза

обновлен
1 Фев '15 0:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru