radmath Feb 15 2022 at 22:46

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

4 min

9.9K

Algorithms*Mathematics*Popular science

From sandbox

+11

Comments 11

bigcrush Feb 16 2022 at 08:14

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

$x_{k}^{3}-x_{l}^{3} = 0$

radmath Feb 16 2022 at 08:32

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

bigcrush Feb 16 2022 at 08:48

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

radmath Feb 16 2022 at 08:55

Указанная разность всегда равна нулю, но для смежных вершин $x_k\neq x_l$ , поэтому x_k^2+x_kx_l +x_l^2=0.

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

bigcrush Feb 16 2022 at 09:39

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

Sergey_Kovalenko Feb 16 2022 at 15:07

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

wataru Feb 16 2022 at 20:16

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

Sergey_Kovalenko Feb 16 2022 at 23:21

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

radmath Feb 21 2022 at 13:44

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

third112 Feb 16 2022 at 19:45

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

third112 Feb 16 2022 at 20:05

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

Show the best of all time