4.1. Простая задача размещения (загрузки).

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

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

<< | >>

↑

Источник: Теория графов. Лекция. 2017

Еще по теме 4.1. Простая задача размещения (загрузки).:

II. КЛАССИЧЕСКАЯ ПОЛИТИЧЕСКАЯ ЭКОНОМИЯ

- Аналитическая геометрия - Вариационное исчисление - Векторный и тензорный анализ - Высшая геометрия - Высшая математика - Вычислительная математика - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комплексное исчисление - Линейная алгебра - Линейное программирование - Математическая логика - Математическая физика - Математический анализ - Пределы - Ряды - Статистика - Теория вероятностей - Теория графов - Теория игр - Теория принятия решений - Теория случайных процессов - Теория чисел - Финансовая математика - Функциональный анализ -

- Антропология - Астрономия - Безопасность жизнедеятельности - Библиотечное дело - Биология - Военное дело - География - Зоология - История - Культурология - Литература - Математика - Медицина - Педагогика - Политология - Право России - Право України - Психология - Религоведение - СМИ и журналистика - Социология - Технические науки - Транспорт - Физика - Философия - Финансы - Экология - Экономика - Этнография и демография - Юриспруденция - Языкознание -