Problem dotyczący minimalnego pokrycia ścieżki

Pracujemy na rozproszonych komputerach i znaleźliśmy problem złożoności, który sprowadza się do minimalnego problemu obejmującego ścieżkę. Obecnie nie wiemy, jak to rozwiązać. Problem jest następujący:

Niech będzie liczbą całkowitą, a będzie wykresem zawierającym wierzchołki . Każdy wierzchołek oznaczamy parą taką, że . Odtąd nazywamy wierzchołki za pomocą ich etykiety. Zestaw krawędzi w jest zdefiniowany następująco: . $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 \}$

Jaka jest minimalna ścieżka pokrycia ? $Z_k$

Czytanie „Problemy z okładką ścieżki w grafach i aplikacjach do testowania programów” Ntafos i in. , widzieliśmy, że minimalne pokrycie ścieżki jest równe kardynalnemu największemu zestawowi wierzchołków nieporównywalnych. Myśleliśmy o następującym zestawie: który ma kardynał . $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ $\frac{k^2}{4}-\frac{k}{2}$

Szczerze,

Pierre

graph-theory co.combinatorics application-of-theory Pierre
źródło

czy w definicji krawędzi powinno być zamiast ?

j^{'} \geq j

$j' \ge j$

j^{'} \geq i

$j' \ge i$

Z_{k}

$Z_k$

Suresh Venkat

Odpowiedzi:

Wygląda na to, że twój wykres jest przejściowo zamkniętym DAG, prawda? Jeśli tak (i prawdopodobnie jest to powtórzenie tego, co mówisz w cytowaniu Ntafos i in.), Minimalna liczba ścieżek potrzebnych do pokrycia DAG to tylko maksymalna liczba nieporównywalnych parami elementów; to jest twierdzenie Dilwortha .

Twój przykład może być na tyle prosty, że można zidentyfikować ten maksymalny nieporównywalny zestaw bezpośrednio, ale ogólnie można znaleźć ten zestaw w czasie wielomianowym za pomocą algorytmu opartego na dopasowywaniu grafów. Sekcja „Dowód przez twierdzenie Königa” artykułu z Wikipedii na temat twierdzenia Dilwortha wyjaśnia, w jaki sposób.

David Eppstein
źródło