Dua pohon merentang minimum

Question

Saya punya masalah dengan latihan ini.

Pertimbangkan grafik non-orientasi $G=(N,E)$, dengan $n=|N|$ dan berat $c_{i,j}$ terkait ke tepi $(i,j)$ di $E$.

1. Pertimbangkan sebuah simpul $a$ di $N$. Tulis model ILP untuk menemukan dua pohon bentang dengan panjang total minimum, tanpa tepi yang sama dan salah satunya memiliki jumlah tepi yang berdekatan$a$ persis sama dengan 3.

2. Pertimbangkan sekarang satu set simpul $S$ di $N$. Tulis model ILP untuk menemukan dua pohon bentang dengan panjang total minimum, tanpa tepi yang sama dan sedemikian rupa sehingga menyentuh simpul dari$S$ dalam cara yang seimbang: tepi datang ke setiap simpul $a$ di $S$ yang digunakan oleh salah satu dari dua pohon tidak boleh lebih dari dua kali tepi yang digunakan oleh pohon lain.

Upaya saya untuk pertanyaan 1.:let $x_{i,j}=1$ jika saya memilih tepi $(i,j)$ untuk pohon itu $T_1$dan 0 sebaliknya. Hal yang sama untuk pohon lainnya$T_2$ dengan label $y_{i,j}$. Ini adalah model ILP saya: \ begin {align} && \ text {minimalkan} \ sum _ {(i, j) \ in E} c_ {i, j} (x_ {i, j} + y_ {i, j}) \\ && \ sum _ {(i, j) \ in E} x_ {i, j} & = n-1 \\ && \ sum _ {(i, j) \ in E} y_ {i, j} & = n -1 \\ && \ jumlah _ {(i, j) \ dalam E (S)} x_ {i, j} & \ leq | S | -1 && \ text {untuk setiap$S\subseteq N$} \\ && \ sum _ {(i, j) \ in E (S)} y_ {i, j} & \ leq | S | -1 && \ text {untuk setiap$S\subseteq N$} \\ && x_ {i, j} + y_ {i, j} & \ le 1 && \ text {untuk setiap $(i,j)\in E$} \\ && \ sum _ {(i, j) \ in \ delta (a)} x_ {i, j} & = 3 \ end {align}

dimana $E(S)=\{(i,j)\in E \,|\, i \in S\, , j \in S \}$ ; $\delta(a)=\{(i,j)\in E \,|\, i =a \text{ or } j = a \}$. Empat kondisi pertama adalah kondisi klasik untuk pohon merentang minimum untuk dihubungkan dan tanpa siklus. Kondisi kelima, pohon tidak memiliki tepi yang sama.

Bagaimana menurut anda? Bagaimana dengan pertanyaan kedua?

Answer 1

Saya membuat beberapa koreksi pada formulasi Anda untuk pertanyaan pertama. Batasan baru yang diperlukan untuk pertanyaan kedua adalah \ begin {align} \ sum _ {(i, j) \ in \ delta (a)} x_ {i, j} & \ le 2 \ sum _ {(i, j) \ in \ delta (a)} y_ {i, j} && \ text {untuk$a\in S$} \\ \ sum _ {(i, j) \ in \ delta (a)} y_ {i, j} & \ le 2 \ sum _ {(i, j) \ in \ delta (a)} x_ {i, j } && \ text {untuk $a\in S$} \ end {align}