Jalur minimum yang mencakup masalah

Kami bekerja di komputer terdistribusi, dan kami menemukan masalah kompleksitas yang mengurangi masalah jalur minimum. Kami saat ini tidak tahu bagaimana menyelesaikannya. Masalahnya adalah sebagai berikut:

Biarkan ada beberapa integer, dan membiarkan Z k menjadi grafik yang berisi k ( k + 1 $k$$Z_k$ simpul. Kami memberi label pada setiap simpul dengan pasangan(i,j)sedemikian sehingga1≤i≤j≤k. Selanjutnya, kami beri nama simpul menggunakan label mereka. Himpunan tepi diZkdidefinisikan sebagai berikut: {((i,j),(i',j'))| i′>i∧j′≥i}.$\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 \}$

Apakah lintasan minimal meliputi dari ?$Z_k$

Membaca "On Path Cover Problem dalam Digraphs dan Aplikasi ke Program Testing" oleh Ntafos et al. , kita telah melihat bahwa penutup jalur minimum sama dengan kardinal dari himpunan simpul terbesar yang tak tertandingi. Kami berpikir tentang himpunan berikut: yang memiliki kardinal k $S= \{ (i,j) : i \geq k/2 \land j < k/2 \}$ .$\frac{k^2}{4}-\frac{k}{2}$

Hormat kami,

Pierre

Sepertinya grafik Anda adalah DAG yang ditutup secara transparan, bukan? Jika demikian (dan ini mungkin merupakan pernyataan ulang dari apa yang Anda katakan dalam kutipan Ntafos et al), jumlah minimum jalur yang diperlukan untuk menutupi DAG hanyalah jumlah maksimum elemen yang tak tertandingi berpasangan; ini adalah teorema Dilworth .

Contoh Anda mungkin cukup sederhana sehingga seseorang dapat mengidentifikasi set maksimum yang tak tertandingi ini secara langsung, tetapi secara umum dimungkinkan untuk menemukan set ini dalam waktu polinomial, dengan algoritma yang didasarkan pada pencocokan grafik. Bagian "Bukti melalui teorema König" dari artikel Wikipedia tentang teorema Dilworth menjelaskan caranya.