Как раскрасить вершины графа

[bigcrush]

Подскажите, почему справедливо равенство, когда множество E содержит ребро {xk, xl}?

[radmath]

Дело в том, что мы красим с помощью кубических корней из единиц, поэтомуи, а разность этих величин тогда равна нулю.

[bigcrush]

Разве это не выполняется для двух произвольных вершин? Почему указанная разность кубов задаёт именно смежные вершины?

[radmath]

Указанная разность всегда равна нулю, но для смежных вершин, поэтому

Постарался переписать абзац, чтобы он был более логичным. Спасибо!

[bigcrush]

Я, думаю, понял. Меня смущало, как равенство нулю последнего трёхчлена гарантирует, что xk!=xl? Но оба множителя в разложении разности кубов могут оказаться нулями, только если xk=xl=0, а это не так, поскольку xi - корень из 1. Спасибо. Простите, за занудство.

[Sergey_Kovalenko]

Ох, ничего себе: Вы (автор статьи) говорите, что есть алгоритм, который позволяет точно определить, совместна ли система алгебраических уравнений или нет. А не вспомните случаем сложность этого алгоритма (в худшем случае) от числа переменных и степени уравнений?

[wataru]

Очевдино, оно экспоненциально, потому что задача раскраски графа NP-complete. Может работает быстрее полного перебора, но не ассимптотически.

[Sergey_Kovalenko]

Да, действительно очевидно.

[radmath]

Думаю, что алгоритмы нахождения базисов Грёбнера имеют сложность похуже экспоненциальной. Но возможно именно для идеалов, которые соответствуют графам, сложность будет получше.

[third112]

В статье ни слова о Теореме о пяти красках и о Теореме о четырёх красках. Это кажется неслучайным! В отношении предложенного алгоритма возникает подозрение, что автор тихой сапой хочет доказать им теорему о четырёх красках. BTW четкое описание алгоритма, как принято в CS, отсутствует его подменяет код реализации, что не является равноценной заменой, т.к. любую ошибку можно будет назвать багом реализации или багом ЯП.

[third112]

PS Вызывает удивление помещение статьи в хаб "Научно-популярное". Если бы речь была об известном знании, то его можно популяризировать. Нпр., теорему Пифагора можно попробовать популярно объяснить 6 летним детям. Но новый алгоритм помещать в "популярное", прежде описания в научных изданиях (можно и в других хабах на Хабре) — явно преждевременно.