Рассмотрим задачу размещения ( загрузки) п каких-то предметов по ящикам. Пусть каждый предмет соответствует определенной ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Кристофайдс Н.N. Теория графов Алгоритмический подход


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

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

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

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