Граф О называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов ( ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Кристофидес Н.N. Теория графов


Граф О называют г-хроматическим, если его вершины могут быть раскрашены с использованием г цветов ( красок) так, что не найдется двух смежных вершин одного цвета. Задача нахождения хроматического числа графа называется задачей о раскраске ( или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на г подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.

(cкачать страницу)

Смотреть книгу на libgen

Граф О называют г-хроматическим,  если его вершины могут быть раскрашены с использованием г цветов ( красок) так,  что не найдется двух смежных вершин одного цвета.  Задача нахождения хроматического числа графа называется задачей о раскраске ( или задачей раскраски) графа.  Соответствующая этому числу раскраска вершин разбивает множество вершин графа на г подмножеств,  каждое из которых содержит вершины одного цвета.  Эти множества являются независимыми,  поскольку в пределах одного множества нет двух смежных вершин.