Чтобы доказать, что 3-раскраска разрешима, достаточно сказать:
- Каждый узел на графике имеет 3 возможных цвета
- Поэтому мы можем перечислить все возможностей и затем проверить, что никакие два ребра не соединяют узлы одного цвета
Означает ли это, что 3-раскраска разрешима? Или мне нужно построить машину Тьюринга для правильного доказательства?
По 3-цветному окрасу я говорю о проблеме раскраски графов; то есть назначить один из 3 цветов каждому узлу в неориентированном графе так, чтобы никакие два соседних узла не имели одинаковый цвет.
Ответы:
Это полностью зависит от того, к какому уровню формальности вы стремитесь. Неформального описания алгоритма в вашем вопросе вполне достаточно, чтобы убедить меня, что 3-окрашиваемость разрешима. Если вы хотите быть более формальным, вы можете указать псевдокод. Если вы хотите быть более формальным, вы можете описать машину Тьюринга на английском языке. Если вы хотите быть еще более формальным, вы можете записать полное описание машины Тьюринга и доказать, что она действительно решает 3-цветность.
Сказав, что из перечисленных вариантов, скорее всего, будет ошибка в описании машины Тьюринга или в ее доказательстве правильности! Так что не ясно, какое доказательство было бы наиболее правдоподобным.
источник
источник