Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.3. Распределение ресурсов

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

6. Задачи

(см. скан)

(см. скан)

(см. скан)

7. Список литературы

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление