граф-1
.docДля нашего примера искомая матрица может иметь следующий вид:
.
Условимся
считать, что строки матрицы пронумерованы
числами 1,2,…,7 сверху вниз и каждая строка
соответствует вершине графа с
соответствующим номером. Столбцам графа
поставим в соответствие символы
(слева направо), где каждый столбец
соответствует некоторому максимальному
независимому подмножеству вершин
рассматриваемого графа. Так, например,
символу (столбцу)
соответствует максимальное независимое
подмножество вершин {2,5,7} ( 1 ставится в
той строке, номер которой соответствует
номеру принадлежащей
вершине, и 0 - в противном случае).
Обозначим через
={
}
множество всех максимально независимых
подмножеств вершин графа G.
Далее из множества
выбираем
минимальное количество таких подножеств,
которые образуют покрытие П = {
}
множества Х вершин графа G.
Напомним,
что покрытием П = {
}
множества вершин Х графа называется
такая совокупность подмножеств, которая
удовлетворяет двум следующим условиям:
1).
,
где Х- множество вершин графа G.
2).
.
Минимальным покрытием множества Х вершин графа называется такое, которое содержит минимальное число подмножеств множества П.
Заметим, что в приведенной выше матрице М перечислены (ради сокращения размерности приводимой матрицы) не все максимальные независимые подмножества вершин графа, однако и этот неполный набор максимальных независимых подмножеств уже даст минимально возможную раскраску, т.е. позволят найти хроматическое число графа.
В нашем примере можно указать по крайней мере два различных минимальных покрытия:
П1={
}=
{{2,4,6},{1,7},{3,5}} и П2=
={{2,5,7},{1,4},{3,6}}.
На основе этих данных получаем две различные раскраски графа, содержащие по три краски.
1) Покрытию П1 соответствует, например, раскраска {2,4,6}- белые,{1,7}- красные,{3,5}- черные.
2). Покрытию П2 соответствует, например, раскраска {2,5,7} - красные,{1,4} - черне,{3,6} - белые.
Докажем
теперь, что полученные раскраски
минимальны по числу использованных
цветов, т.е. хроматическое число
(G)
графа в нашем примере равно 3.
В
нашем исходном графе имеется подграф,
изображенный на рис.3, который, как легко
видеть, требует для раскраски ровно три
цвета. Следовательно, исходный граф
также не может быть раскрашен меньшим
числом красок. Однако такие раскраски
(два варианта) мы указали в явном виде,
следовательно, хроматическое число
(G)
графа действительно равно 3.
1
3
Рис.3.
В заключение отметим, что в общем случае задача раскраски вершин графа имеет не единственное решение.
Ниже на рис.4 приведен один из вариантов раскраски рассматриваемого графа.
Рис.4