Вероятностный подход при решении задач на раскраску заключается в использовании вероятностных алгоритмов, которые позволяют допускать, что вычисления в некоторых случаях не завершаются или дают неправильный ответ. 1

Некоторые методы вероятностного подхода:

• Сведение к полиномиальной задаче. 1 Для каждой вершины случайным образом назначают пару цветов, в которые её можно покрасить. 1 Для случая, когда для каждой из вершин необходимо выбрать один из двух цветов, существует полиномиальный алгоритм. 1 Многократное повторение такой операции даёт вероятностный алгоритм. 1
• Изменение порядка шагов. 1 Переменные переупорядочивают случайным образом и в этом порядке им рекурсивно присваивают некоторые значения. 1
• Вероятностный локальный поиск. 1 Вместо того чтобы перебирать все варианты изменений, каждый раз пытаются производить изменения случайным образом. 1 Тогда с определённой вероятностью ответ, если он существует, будет найден. 1

Вероятностный метод является мощным инструментом получения результатов в дискретной математике и играет важную роль в теории компьютерных вычислений. 4