5.3. Маршруты полетов самолетов [1, 55, 64, 65]

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

Укажем еще на одну разновидность рассмотренной задачи (также часто встречающуюся при назначении маршрутов полетов). Если требовать, чтобы каждый этап содержался только в одном маршруте, то приходим к ЗНР, соответствующей сформулированной выше ЗНП.