5.2. Составление графиков осмотра (проверки)

В задачах теории расписаний осмотры представляются в виде временных интервалов. Каждому осмотру можно сопоставить вершину некоторого графа, причем две любые вершины графа будут соединены ребром лишь тогда, когда соответствующие им осмотры нельзя осуществлять одновременно. Требуется составить такой график осмотра, который связан с наименьшими временными затратами (с учетом приведенных выше ограничений на «совместимость» осмотров). Эта задача эквивалентна задаче о раскраске вершин графа с использованием наименьшего числа цветов. Хроматическое число графа как раз и соответствует осмотру, требующему наименьших временных затрат.

Если число осмотров, которые можно осуществлять в одно и то же время, ограничено (например, из-за размеров помещения), то приходим к задаче типа (i) из разд. 5.1, и в этом случае является числом помещений, где происходит осмотр.