Раскрашивание графика с помощью первого обхода глубины

Я знаю, что для раскраски узлов графа обычным решением является возврат / грубая сила. Но мне было интересно, могу ли я с помощью DFS найти решение?

Отслеживание с возвратом дает вам возможность вернуться и попробовать другой вариант цвета, чтобы окрасить все узлы N цветами.

DFS начнется с одного узла и раскрасит его, затем перейдет к своему соседу и раскрасит его другим цветом, чем его соседи и т. Д.

Я попытался использовать этот метод, но не нашел алгоритма, который бы его использовал.

Вопрос: Возможно ли использование DFS для раскраски узлов графа. Если да, то является ли это более эффективным, чем отслеживание с возвратом?

Спасибо


graph graph-coloring brute-force depth-first-search
person CMPS    schedule 18.08.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я считаю, что есть некоторая путаница при сравнении отслеживания с возвратом и раскраски вершин DFS. Обход DFS для графа дает полное перечисление его вершин в последовательности, связанной с его структурой. Тем не менее, он не является полным перечислением проблемы раскраски вершин, которое потребовало бы учета возможных цветов вершин.

Таким образом, если я правильно понимаю, вы реализовали жадную эвристическую раскраску для графа, управляемого DFS. С другой стороны, решение с возвратом / перебором, как вы его называете (например, [Randall-Brown 72]) предоставит точное решение проблемы минимальной раскраски, поскольку она рассматривает все возможные раскраски вершин. Обратите внимание, что обход DFS можно использовать для первоначальной сортировки вершин (топологическая сортировка) и передачи этого порядка точному решателю.

person chesslover    schedule 27.08.2014
comment
Так в принципе DFS не гарантирует минимум K раскраски вершин? Спасибо - person CMPS; 28.08.2014
comment
Если вы обратитесь к обходу DFS без возврата к выбору цвета, этого не произойдет. - person chesslover; 28.08.2014