Графовая модель распределения локомотивов для грузовых перевозок на линейном участке железной дороги. Задача о максимальном по включению покрытии графика

Работа посвящена формальной постановке и решению задачи, возникающей при распределении локомотивов между составами для осуществления грузовых железнодорожных перевозок с заранее заданным графиком. Цель состоит в том, чтобы определить, достаточно ли число локомотивов при заданном их начальном расположении для выполнения всех перевозок. Решение представлено в виде алгоритма, строящего покрытие графика: полное, если оно существует, или, в противном случае, частичное – максимальное по включению. Доказана теорема о взаимно однозначном соответствии существования полного покрытия и достаточности числа локомотивов.