раскраска графа и NP-полнота

У меня проблемы с пониманием NP-полноты раскраски графа.

Если я предполагаю жадную стратегию раскраски (http://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring) с DFS, то, похоже, я смогу оптимально раскрасить графики. Может ли кто-нибудь помочь мне с контрпримером?

Чтобы было ясно, пусть все узлы будут окрашены в -1. Раскрасьте начальный узел 1. Продолжайте обход в глубину, раскрашивая каждый узел минимальным целым числом, которое еще не назначено его соседям. Когда это не сможет оптимально раскрасить график?


graph algorithm np-complete
person user1170883    schedule 19.08.2012    source источник
comment
Вы хоть читали страницу в Википедии? В нем говорится: Качество результирующей раскраски зависит от выбранного порядка. . . С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на n вершинах может быть двухцветным, но его порядок приводит к жадной раскраске n/2 цветов.   -  person Ted Hopp    schedule 19.08.2012
comment
Я читал и не стал бы спрашивать, понял ли я. Я попробовал график короны на соседней картинке и по ссылке, которая ведет к статье о графике короны с различными порядками DFS. Я понимаю, что заказ BFS не удастся. Я не нашел такого заказа DFS.   -  person user1170883    schedule 19.08.2012
comment
@TedHopp: эта плохая жадная окраска графа короны не может быть сгенерирована из жадной окраски DFS.   -  person Keith Randall    schedule 19.08.2012

Ответы (1)


arrow_upward
0
arrow_downward

Жадная раскраска DFS определенно не работает на некоторых графах. Чтобы придумать контрпример, нужно попытаться написать доказательство того, что DFS будет раскрашивать оптимально. Часть доказательства того, что вы не можете приступить к работе, — это подсказка, чтобы придумать контрпример.

person Keith Randall    schedule 19.08.2012