Покрытие пути
Для ориентированного графа G = ( V , E ) покрытие путей — это набор ориентированных путей , в котором каждая вершина v ∈ V принадлежит хотя бы одному пути. Обратите внимание, что покрытие пути может включать пути длиной 0 (одна вершина). [1]
Покрытие пути может также относиться к покрытию пути, не пересекающегося по вершинам , то есть к множеству путей, в котором каждая вершина v ∈ V принадлежит ровно одному пути. [2]
Характеристики
[ редактировать ]Теорема Галлая и Милгрэма показывает, что число путей в наименьшем покрытии путей не может быть больше числа вершин в наибольшем независимом множестве . [3] В частности, для любого графа G существует покрытие путей P и независимое множество I такие, что содержит ровно одну вершину из каждого пути в P. I Теорема Дилворта является следствием этого результата.
Вычислительная сложность
[ редактировать ]Для ориентированного графа G задача минимального покрытия путей состоит в поиске покрытия путей для G с наименьшим количеством путей.
Минимальное покрытие путей состоит из одного пути тогда и только тогда, когда существует гамильтонов путь в G . Гамильтонова задача пути является NP-полной , и, следовательно, задача минимального покрытия пути является NP-трудной . Однако, если граф ациклический, проблема относится к классу сложности P и, следовательно, может быть решена за полиномиальное время путем преобразования ее в задачу сопоставления , см. https://walkccc.me/CLRS/Chap26/Problems/26-2/. .
Приложения
[ редактировать ]Приложения минимального пути включают тестирование программного обеспечения. [4] Например, если граф G представляет все возможные последовательности выполнения компьютерной программы, то покрытие пути — это набор тестовых прогонов, который охватывает каждый оператор программы хотя бы один раз.
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Дистель (2005) , Раздел 2.5.
- ^ Францблау и Райчаудхури (2002) .
- ^ Дистель (2005) , Теорема 2.5.1.
- ^ Нтафос и Хакими (1979)
Ссылки
[ редактировать ]- Банг-Йенсен, Йорген; Гутин, Грегори (2006), Орграфы: теория, алгоритмы и приложения (1-е изд.), Springer .
- Дистель, Рейнхард (2005), Теория графов (3-е изд.), Springer .
- Францблау, Д.С.; Райчаудхури, А. (2002), «Оптимальные гамильтоновы пополнения и покрытия путей для деревьев, а также приведение к максимальному потоку» , ANZIAM Journal , 44 (2): 193–204, doi : 10.1017/S1446181100013894 .
- Нтафос, Южная Каролина; Хакими, С. Луи. (1979), «О проблемах покрытия путей в орграфах и приложениях для тестирования программ», IEEE Transactions on Software Engineering , 5 (5): 520–529, doi : 10.1109/TSE.1979.234213 .