Minimum iki uzanan ağaç

Question

Bu egzersizle ilgili bir sorunum var.

Yönsüz bir grafik düşünün $G=(N,E)$, ile $n=|N|$ ve ağırlık $c_{i,j}$ kenarlarla ilişkili $(i,j)$ içinde $E$.

1. Bir tepe noktası düşünün $a$ içinde $N$. ILP modelini, minimum toplam uzunluğa sahip, ortak kenarları olmayan ve içlerinden birinin, olay yerine gelen kenarların sayısına sahip olduğu iki yayılma ağacı bulmak için yazın.$a$ tam olarak 3'e eşittir.

2. Şimdi bir dizi tepe noktası düşünün $S$ içinde $N$. ILP modelini, minimum toplam uzunluğa sahip, ortak kenarları olmayan ve köşelerine değecek şekilde iki yayılan ağacı bulmak için yazın.$S$ dengeli bir şekilde: her tepe noktasına olay kenarları $a$ içinde $S$ iki ağaçtan biri tarafından kullanılan, diğer ağaç tarafından kullanılan kenarların iki katından fazla olamaz.

Soru 1.:let için girişimim $x_{i,j}=1$ kenarı seçersem $(i,j)$ ağaç için $T_1$ve 0 aksi takdirde. Diğer ağaç için de aynı$T_2$ etiketlerle $y_{i,j}$. Bu benim ILP modelim: \ begin {hizala} && \ text {küçült} \ 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 \\ && \ sum _ {(i, j) \ in E (S)} x_ {i, j} & \ leq | S | -1 && \ text {her biri için$S\subseteq N$} \\ && \ sum _ {(i, j) \ içinde E (S)} y_ {i, j} & \ leq | S | -1 && \ text {her biri için$S\subseteq N$} \\ && x_ {i, j} + y_ {i, j} & \ le 1 && \ text {her biri için $(i,j)\in E$} \\ && \ sum _ {(i, j) \ in \ delta (a)} x_ {i, j} & = 3 \ end {hizala}

nerede $E(S)=\{(i,j)\in E \,|\, i \in S\, , j \in S \}$ ; $\delta(a)=\{(i,j)\in E \,|\, i =a \text{ or } j = a \}$. İlk dört koşul, asgari genişleyen ağaçların bağlanması ve döngüsüz olması için klasik koşullardır. Beşinci koşul, ağaçların ortak kenarlarının olmamasıdır.

Ne düşünüyorsun? Ya ikinci soru?

Answer 1

İlk soru için formülasyonunuzda birkaç düzeltme yaptım. İkinci soru için gereken yeni kısıtlamalar şunlardır: \ begin {align} \ sum _ {(i, j) \ in \ delta (a)} x_ {i, j} & \ le 2 \ sum _ {(i, j) \ in \ delta (a)} y_ {i, j} && \ text {için$a\in S$} \\ \ toplam _ {(i, j) \ in \ delta (a)} y_ {i, j} & \ le 2 \ sum _ {(i, j) \ in \ delta (a)} x_ {i, j } && \ text {için $a\in S$} \ end {hizala}