stringtranslate.com

Покрытие пути

Для направленного графа G  = ( V ,  E ) покрытие путей — это набор направленных путей , такой, что каждая вершина v  ∈  V принадлежит по крайней мере одному пути. Обратите внимание, что покрытие путей может включать пути длины 0 (одна вершина). [1]

Покрытие путей может также относиться к покрытию путей с непересекающимися вершинами , т. е. к набору путей, такому, что каждая вершина v  ∈  V принадлежит ровно одному пути. [2]

Характеристики

Теорема Галлаи и Милгрэма показывает, что число путей в наименьшем покрытии путей не может быть больше числа вершин в наибольшем независимом множестве . [3] В частности, для любого графа G существует покрытие путей P и независимое множество I, такие что I содержит ровно одну вершину из каждого пути в P. Теорема Дилворта вытекает как следствие этого результата .

Сложность вычислений

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

Минимальное покрытие пути состоит из одного пути тогда и только тогда, когда в G существует гамильтонов путь . Задача о гамильтоновом пути является NP-полной , и, следовательно, задача о минимальном покрытии пути является NP-трудной . Однако, если граф ациклический, задача имеет класс сложности P и, следовательно, может быть решена за полиномиальное время путем преобразования ее в задачу сопоставления , см. https://walkccc.me/CLRS/Chap26/Problems/26-2/.

Приложения

Приложения минимального покрытия пути включают тестирование программного обеспечения. [4] Например, если граф G представляет все возможные последовательности выполнения компьютерной программы, то покрытие пути представляет собой набор тестовых запусков, который охватывает каждый оператор программы по крайней мере один раз. Другое применение проблемы минимального покрытия пути заключается в поиске минимального количества автопарков и оптимальной диспетчеризации их для обслуживания спроса на мобильность в городе. [5]

Смотрите также

Примечания

  1. ^ Дистель (2005), Раздел 2.5.
  2. ^ Францблау и Райчаудхури (2002).
  3. ^ Дистель (2005), Теорема 2.5.1.
  4. ^ Нтафос и Хакими (1979)
  5. ^ Вазифех, ММ; Санти, П.; Реста, Г.; Строгац, Ш.; Ратти, К. (май 2018 г.). «Решение проблемы минимального парка транспортных средств в городской мобильности по требованию». Nature . 557 (7706): 534–538. doi :10.1038/s41586-018-0095-1. ISSN  1476-4687.

Ссылки