Оптимальная раскраска вершин графа
09.03.2012 |Пусть граф G = (V,E) правильно раскрашен. Вершины, окрашенные в один цвет, образуют внутреннее устойчивое множество вершин в G. Хроматическое число графа G можно определить как минимальное число внутренне устойчивых множеств, в сумме дающих все множество V. Такое минимальное покрытие можно найти следующим образом. Пусть S1, S2, …,Sк – есть все максимальные внутренне устойчивые множества вершин в G. С каждым Si свяжем логическую переменную XSi означающую, что вершина v ∈Si. Построим логическую формулу – условие оптимальной раскраски вершин графа G: F = &v∈V(∨v∈SiXSi). Взяв по одной переменной в каждой скобке формулы F, получим некоторую конъюнкцию XSa*XSb*…*XSc, для которой семейство внутренне устойчивых множеств {Sa, Sb,…,Sc} в сумме покрывает все множество V. Пусть ∨iKi – есть минимальная ДНФ D для формулы F. Пусть дизъюнктивному слагаемому Ki = XSj1*XSj2*…*XSjk в D соответствует наименьшее по длине k семейство Li = {Sj1, Sj2,…,Sjk} новых вершин. Хроматическое число χ(G) = k. Ему соответствует следующая оптимальная раскраска вершин графа G. В цвета 1,2,…, k последовательно окрашено семейство вершин Sj1, Sj2-Sj1, Sj3-(Sj1∪Sj2),…., Sjk – (Sj1∪…∪Sjk-1) соответственно.
Алгоритм оптимальной раскраски (p,q)-графа G=(V,E)
1) Построить все максимальные внутренне устойчивые множества вершин S1, …, Sr.
2) Построить логическую формулу F, являющуюся условием оптимальной раскраски графа G: F = &v∈V (∨v∈Sixsi)
3) Построить минимальную ДНФ для F.
4) Каждому дизъюнктивному слагаемому ki = xSa, xSb, …, xSc в D соответствует минимальное семейство Li = {Sa, Sb, …, Sc) внутренне устойчивых множеств Sa, Sb, …, Sc. Из всех Li выбираем наименьшее по длине k семейство {Sj1, Sj2, …, Sjk}. Хроматическое число χ(G)=k. Ему соответствует следующая оптимальная раскраска вершин графа G. В цвета 1,2,…,k последовательно раскрашиваем семейство вершин Sj1, Sj2-Sj1, Sj3-(Sj1∪Sj2),…., Sjk – (Sj1∪…∪Sjk-1).
