Brélaz минимальная окраска

Question

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

Может ли кто-нибудь подтвердить это и дать мне пример графика, который бы это доказал?

Answer 1

Brélaz - эвристика для раскраски вершин 70-х годов, также известная как DSATUR (степень насыщения). Известно, что он особенно хорош с графами Эрдеша-Реньи (равномерная случайная выборка) и обеспечивает хороший компромисс между усилием и напряженностью.

Однако это всего лишь эвристика, и она не может подтвердить оптимальность.

Brélaz также может использоваться в схеме полного перечисления, как описано в [Randall-Brown 72], но я думаю, что это не то, что вы реализовали.

По сравнению с DSATUR также произошли некоторые улучшения, в основном касающиеся разрыва связей

1. Сьюэлл 1996
2. Сан Сегундо 2012 (алгоритм PASS)