Рассмотрим задачу размещения ( загрузки) п каких-то предметов по ящикам. Пусть каждый предмет соответствует определенной ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Кристофайдс Н.N.
Теория графов Алгоритмический подход
Рассмотрим задачу размещения ( загрузки) п каких-то предметов по ящикам. Пусть каждый предмет соответствует определенной вершине графа G. Если ящики имеют неограниченную вместимость, так что в каждый из них можно поместить сколько угодно предметов, то задача нахождения наименьшего числа ящиков для размещения предметов эквивалентна задаче нахождения хроматического числа графа G; причем каждому ящику соответствует определенный цвет, а предметы, окрашенные в один цвет, укладываются в один и тот же ящик.