Минимальная проблема покрытия пути

Мы работаем с распределенными компьютерами, и мы столкнулись с проблемой сложности, которая сводит к минимуму проблему с маршрутом. В настоящее время мы не знаем, как ее решить. Проблема заключается в следующем:

Пусть - некоторое целое число, а - граф, содержащий вершин. Мы помечаем каждую вершину парой такой что . Далее мы называем вершины, используя их метки. Множество ребер в определяется следующим образом: . $k$ $Z_k$ $\frac{k(k+1)}{2}$ $(i,j)$ $1 \leq i \leq j \leq k$ $Z_k$ $\{ ((i,j),(i',j')) | i' >i \land j' \geq i \}$

Каково минимальное покрытие пути ? $Z_k$

Чтение "Nathfos et al." "Проблемы покрытия пути в орграфах и приложениях к тестированию программ". Мы видели, что минимальное покрытие пути равно кардиналу наибольшего несравнимого множества вершин. Мы думали о следующем наборе: с кардиналом . $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ $\frac{k^2}{4}-\frac{k}{2}$

С уважением,

пьер

graph-theory co.combinatorics application-of-theory пьер
источник

это должно быть вместо в определении ребра ?

j^{'} \geq j

$j' \ge j$

j^{'} \geq i

$j' \ge i$

Z_{k}

$Z_k$

Суреш Венкат

Ответы:

Похоже, ваш график транзитивно замкнутый DAG, верно? Если это так (а это, вероятно, подтверждение того, что вы говорите в своей цитате из Ntafos и др.), Минимальное количество путей, необходимых для покрытия DAG, - это только максимальное количество попарно несопоставимых элементов; это теорема Дилворта .

Ваш пример может быть достаточно простым, чтобы можно было напрямую идентифицировать этот максимальный несопоставимый набор, но в целом этот набор можно найти за полиномиальное время с помощью алгоритма, основанного на сопоставлении графов. Раздел «Доказательство с помощью теоремы Кёнига» статьи в Википедии о теореме Дилворта объясняет как.

Дэвид Эппштейн
источник