Gomory-Hu ağacı - Gomory–Hu tree

İçinde kombinatoryal optimizasyon, Gomory-Hu ağacı^[1] Kapasiteleri olan yönsüz bir grafiğin ağırlığı ağaç minimumu temsil eden s-t herkes için kesintiler s-t grafikteki çiftler. Gomory – Hu ağacı |V | − 1 maksimum akış hesaplamalar.

Tanım

İzin Vermek G = ((V_G, E_G), c) ile yönsüz bir grafik olmak c(sen,v) kenarın kapasitesi olmak (sen,v) sırasıyla.

Minimum kapasitesini belirtin s-t λ tarafından kesildi_st her biri için s, t ∈ V_G.

İzin Vermek T = (V_G, E_T) bir ağaç olmak, bir kenar kümesini göstermek s-t yol P_st her biri için s, t ∈ V_G.

Sonra T olduğu söyleniyor Gomory-Hu ağacı nın-nin Geğer her biri için s, t ∈ V_G

λ_st = dk_{e∈P_st} c(S_e, T_e),

nerede

S_e, T_e ⊆ V_G birbirine bağlı iki bileşenidir T∖{e}, ve böylece (S_e, T_e) erkek için s-t kesilmiş G.
c(S_e, T_e) kesme kapasitesidir G.

Algoritma

Gomory – Hu Algoritması

Giriş: Yönlendirilmemiş ağırlıklı bir grafik G = ((V_G, E_G), c)

Çıktı: Bir Gomory – Hu Ağacı T = (V_T, E_T).

1. Ayarla V_T = {V_G} ve E_T = ∅.

2. Birkaçını seçin X∈V_T ile | X | ≥ 2 ise X var. Aksi takdirde 6. adıma gidin.

3. Her bağlı bileşen için C = (V_C, E_C) içinde T∖X. İzin Vermek S_C = ∪_{v_T∈V_C} v_T. İzin Vermek S = { S_C | C bağlı bir bileşendir T∖X}.

Oluşturmak için bileşenleri sözleşme G' = ((V_{G '}, E_{G '}), c'), nerede

V_{G '} = X ∪ S.

E_{G '} = E_G|_{X × X} ∪ {(sen, S_C) ∈ X×S | (sen,v)∈E_G bazı v∈S_C} ∪ {(S_C1, S_C2) ∈ S ×S | (sen,v)∈E_G bazıları içinS_C1 ve v∈S_C2}.

c' : V_{G '}×V_{G '}→R⁺ kapasite işlevi şu şekilde tanımlanır:

Eğer (sen,S_C)∈E_G|_{X × S}, c'(sen,S_C) = Σ_{v∈S_C: (u, v) ∈E_G}c(sen,v),
Eğer (S_C1,S_C2)∈E_G|_{S × S}, c'(S_C1,S_C2) = Σ_{(u, v) ∈E_G: u∈S_C1∧v∈S_C2} c(sen,v),
c'(sen,v) = c(sen,v) aksi takdirde.

4. İki köşe seçin s, t ∈ X ve minimum bul s-t kesmek (Bir',B') içinde G'.

Ayarlamak Bir = (∪_{S_C∈Bir'∩S} S_C) ∪ (Bir' ∩ X) ve B = (∪_{S_C∈B'∩S} S_C) ∪ (B' ∩ X).

5. Ayarlayın V_T = (V_T∖X) ∪ {Bir ∩ X, B ∩ X}.

Her biri için e = (X, Y) ∈ E_T yapmak

Eğer Y ⊂ Bir, Ayarlamak e' = (Bir ∩ X, Y), aksi takdirde ayarlayın e' = (B ∩ X, Y).

Ayarlamak E_T = (E_T∖{e}) ∪ {e'} ve w(e') = w(e).

Ayarlamak E_T = E_T ∪ {(Bir∩X, B∩X)}.

Ayarlamak w((Bir∩X, B∩X)) = c'(Bir', B').

2. adıma gidin.

6. Her birini değiştirin {v} ∈ V_T tarafından v ve her biri ({sen},{v}) ∈ E_T tarafından (sen,v). Çıktı T.

Analiz

Kullanmak alt modüler kapasite işlevinin özelliği c, birinde var

c(X) + c(Y) ≥ c(X ∩ Y) + c(X ∪ Y).

Daha sonra minimumun s-t kesilmiş G'ayrıca minimumdur s-t kesilmiş G herhangi s, t ∈ X.

Bunu herkese göstermek için (P, Q) ∈ E_T, w(P,Q) = λ_pq bazı p ∈ P, q ∈ Q algoritma boyunca aşağıdaki Lemma kullanılır,

Herhangi ben, j, k içinde V_G, λ_ik ≥ dk (λ_ij, λ_jk).

Lemma çıktının tekrar tekrar kullanılabileceğini göstermek için tekrar kullanılabilir. T Gomory – Hu Ağacının özelliklerini karşılar.

Misal

Aşağıdaki Gomory – Hu algoritmasının bir simülasyonudur.

yeşil daireler köşeleridir T.
kırmızı ve mavi daireler içindeki köşelerdir G'.
gri köşeler seçilmiş s ve t.
kırmızı ve mavi renklendirme temsil eder s-t kesmek.
çizgili kenarlar s-t kesim seti.
Bir daire içine alınmış köşe kümesidir kırmızı ve B daire içine alınmış köşe kümesidir mavi.

	G'	T

	1. Ayarla V_T = {V_G} = {{0, 1, 2, 3, 4, 5}} ve E_T = ∅. 2. O zamandan beri V_T sadece bir tepe noktasına sahiptir, seçin X = V_G = {0, 1, 2, 3, 4, 5}. Unutmayın \| X \| = 6 ≥ 2.
1.
	3. O zamandan beri T∖X = ∅, kasılma yok ve bu nedenle G' = G. 4. Seçin s = 1 ve t = 5. Minimum s-t kesmek (Bir', B') ({0, 1, 2, 4}, {3, 5}) ile c'(Bir', B') = 6. Ayarlamak Bir = {0, 1, 2, 4} ve B = {3, 5}. 5. Ayarlayın V_T = (V_T∖X) ∪ {Bir ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3, 5} }. Ayarlamak E_T = { ({0, 1, 2, 4}, {3, 5}) }. Ayarlamak w( ({0, 1, 2, 4}, {3, 5}) ) = c'(Bir', B') = 6. 2. adıma gidin. 2. Seçin X = {3, 5}. Unutmayın \| X \| = 2 ≥ 2.
2.
	3. {0, 1, 2, 4} şuraya bağlı bileşendir: T∖X ve böylece S = { {0, 1, 2, 4} }. Oluşturmak için {0, 1, 2, 4} sözleşmesi yapın G', nerede c'( (3, {0, 1, 2 ,4}) ) = c( (3, 1) ) + c( (3, 4) ) = 4. c'( (5, {0, 1, 2, 4}) ) = c( (5, 4) ) = 2. c'( (3, 5)) = c( (3, 5) ) = 6. 4. Seçin s = 3, t = 5. Minimum s-t kesmek (Bir', B') içinde G'({{0, 1, 2, 4}, 3}, {5}) ile c'(Bir', B') = 8. Ayarlamak Bir = {0, 1, 2, 3, 4} ve B = {5}. 5. Ayarlayın V_T = (V_T∖X) ∪ {Bir ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3}, {5} }. Dan beri (X, {0, 1, 2, 4}) ∈ E_T ve {0, 1, 2, 4} ⊂ Bir, ile değiştir (Bir ∩ X, Y) = ({3}, {0, 1, 2 ,4}). Ayarlamak E_T = {({3}, {0, 1, 2, 4}), ({3}, {5})} ile w(({3}, {0, 1, 2 ,4})) = w((X, {0, 1, 2, 4})) = 6. w(({3}, {5})) = c'(Bir', B') = 8. 2. adıma gidin. 2. Seçin X = {0, 1, 2, 4}. Unutmayın \| X \| = 4 ≥ 2.
3.
	3. {{3}, {5}} şuraya bağlı bileşendir T∖X ve böylece S = { {3, 5} }. Oluşturmak için {3, 5} ile sözleşme yapın G', nerede c'( (1, {3, 5}) ) = c( (1, 3) ) = 3. c'( (4, {3, 5}) ) = c( (4, 3) ) + c( (4, 5) ) = 3. c'(sen,v) = c(sen,v) hepsi için sen,v ∈ X. 4. Seçin s = 1, t = 2. Minimum s-t kesmek (Bir', B') içinde G'({1, {3, 5}, 4}, {0, 2}) ile c'(Bir', B') = 6. Ayarlamak Bir = {1, 3, 4, 5} ve B = {0, 2}. 5. Ayarlayın V_T = (V_T∖X) ∪ {Bir ∩ X, B ∩ X} = { {3}, {5}, {1, 4}, {0, 2} }. Dan beri (X, {3}) ∈ E_T ve {3} ⊂ Bir, ile değiştir (Bir ∩ X, Y) = ({1, 4}, {3}). Ayarlamak E_T = {({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4})} w(({1, 4}, {3})) = w((X, {3})) = 6. w(({0, 2}, {1, 4})) = c'(Bir', B') = 6. 2. adıma gidin. 2. Seçin X = {1, 4}. Unutmayın \| X \| = 2 ≥ 2.
4.
	3. {{3}, {5}}, {{0, 2}} şuradaki bağlı bileşenlerdir: T∖X ve böylece S = { {0, 2}, {3, 5} } Oluşturmak için {0, 2} ve {3, 5} ile sözleşme yapın G', nerede c'( (1, {3, 5}) ) = c( (1, 3) ) = 3. c'( (4, {3, 5}) ) = c( (4, 3) ) + c( (4, 5) ) = 3. c'( (1, {0, 2}) ) = c( (1, 0) ) + c( (1, 2) ) = 2. c'( (4, {0, 2}) ) = c( (4, 2) ) = 4. c'(sen,v) = c(sen,v) hepsi için sen,v ∈ X. 4. Seçin s = 1, t = 4. Minimum s-t kesmek (Bir', B') içinde G'({1, {3, 5}}, {{0, 2}, 4}) ile c'(Bir', B') = 7. Ayarlamak Bir = {1, 3, 5} ve B = {0, 2, 4}. 5. Ayarlayın V_T = (V_T∖X) ∪ {Bir ∩ X, B ∩ X} = { {3}, {5}, {0, 2}, {1}, {4} }. Dan beri (X, {3}) ∈ E_T ve {3} ⊂ Bir, ile değiştir (Bir ∩ X, Y) = ({1}, {3}). Dan beri (X, {0, 2}) ∈ E_T ve {0, 2} ⊂ B, ile değiştir (B ∩ X, Y) = ({4}, {0, 2}). Ayarlamak E_T = {({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4})} w(({1}, {3})) = w((X, {3})) = 6. w(({4}, {0, 2})) = w((X, {0, 2})) = 6. w(({1}, {4})) = c'(Bir', B') = 7. 2. adıma gidin. 2. Seçin X = {0, 2}. Unutmayın \| X \| = 2 ≥ 2.
5.
	3. {{1}, {3}, {4}, {5}} şuraya bağlı bileşendir T∖X ve böylece S = { {1, 3, 4, 5} }. Oluşturmak için {1, 3, 4, 5} sözleşmesi G', nerede c'( (0, {1, 3, 4, 5}) ) = c( (0, 1) ) = 1. c'( (2, {1, 3, 4, 5}) ) = c( (2, 1) ) + c( (2, 4) ) = 5. c'( (0, 2) ) = c( (0, 2) ) = 7. 4. Seçin s = 0, t = 2. Minimum s-t kesmek (Bir', B') içinde G'({0}, {2, {1, 3, 4, 5}}) ile c'(Bir', B') = 8. Ayarlamak Bir = {0} ve B = {1, 2, 3 ,4 ,5}. 5. Ayarlayın V_T = (V_T∖X) ∪ {Bir ∩ X, B ∩ X} = { {3}, {5}, {1}, {4}, {0}, {2} }. Dan beri (X, {4}) ∈ E_T ve {4} ⊂ B, ile değiştir (B ∩ X, Y) = ({2}, {4}). Ayarlamak E_T = {({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2} ) } ile w(({2}, {4})) = w((X, {4})) = 6. w(({0}, {2})) = c'(Bir', B') = 8. 2. adıma gidin. 2. yok X∈V_T ile \| X \| ≥ 2. Bu nedenle, 6. adıma gidin.
6.
	6. Değiştirin V_T = {{3}, {5}, {1}, {4}, {0}, {2}}, {3, 5, 1, 4, 0, 2}. Değiştir E_T = {({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2} )} {(1, 3), (3, 5), (2, 4), (1, 4), (0, 2)} tarafından. Çıktı T. Tam olarak \|V \| - 1 = 6 - 1 = 5 kez min-cut hesabı yapılır.

Uygulamalar: Sıralı ve Paralel

Gusfield'ın algoritması, bir Gomory-Hu Ağacı oluşturmanın uygulanmasını basitleştiren, aynı çalışma süresi karmaşıklığında herhangi bir köşe daralması olmaksızın bir Gomory-Hu ağacı bulmak için kullanılabilir.^[2]

Andrew V. Goldberg ve K. Tsioutsiouliklis, Gomory-Hu algoritmasını ve Gusfield algoritmasını uyguladı ve deneysel bir değerlendirme ve karşılaştırma yaptı.^[3]

Cohen vd. Gusfield algoritmasının sırasıyla OpenMP ve MPI kullanan iki paralel uygulamasına ilişkin sonuçları rapor edin.^[4]

Ilgili kavramlar

İçinde düzlemsel grafikler Gomory – Hu ağacı, minimum ağırlığın iki katıdır döngü temeli Gomory-Hu ağacının kesimlerinin, ikili grafik minimum ağırlık döngüsü temelini oluşturan.^[5]

Ayrıca bakınız

Referanslar

^ Gomory, R. E.; Hu, T. C. (1961). "Çok terminalli ağ akışları". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 551–570. doi:10.1137/0109047.
^ Gusfield, Dan (1990). "Tüm Çiftler İçin Çok Basit Yöntemler Ağ Akışı Analizi". SIAM J. Comput. 19 (1): 143–155. doi:10.1137/0219009.
^ Goldberg, A. V .; Tsioutsiouliklis, K. (2001). "Kesilmiş Ağaç Algoritmaları: Deneysel Bir Çalışma". Algoritmalar Dergisi. 38 (1): 51–83. doi:10.1006 / jagm.2000.1136.
^ Cohen, J .; L. A. Rodrigues; F. Silva; R. Carmo; A. Guedes; E. P. Duarte Jr. (2011). "Gusfield'ın Kesme Ağacı Algoritmasının Paralel Uygulamaları". Bilgisayar Bilimlerinde Ders Notları (LNCS). 7016. Springer. 7016 (11th International Conference Algorithms and Architectures for Parallel Processing (ICA3PP)): 258-269. doi:10.1007/978-3-642-24650-0_22. ISBN 978-3-642-24649-4. ISSN 0302-9743.
^ Hartvigsen, D .; Mardon, R. (1994). "Tüm çiftler minimum kesim problemi ve düzlemsel grafiklerde minimum döngü temel problemi". SIAM J. Ayrık Matematik. 7 (3): 403–418. doi:10.1137 / S0895480190177042..

B. H. Korte, Jens Vygen (2008). "8.6 Gomory – Hu Ağaçları". Kombinatoryal Optimizasyon: Teori ve Algoritmalar (Algoritmalar ve Kombinatorikler, 21). Springer Berlin Heidelberg. pp.180 –186. ISBN 978-3-540-71844-4.

[1] Gomory, R. E.; Hu, T. C. (1961). "Çok terminalli ağ akışları". Journal of the Society for Industrial and Applied Mathematics. 9 (4): 551–570. doi:10.1137/0109047.

[2] Gusfield, Dan (1990). "Tüm Çiftler İçin Çok Basit Yöntemler Ağ Akışı Analizi". SIAM J. Comput. 19 (1): 143–155. doi:10.1137/0219009.

[3] Goldberg, A. V .; Tsioutsiouliklis, K. (2001). "Kesilmiş Ağaç Algoritmaları: Deneysel Bir Çalışma". Algoritmalar Dergisi. 38 (1): 51–83. doi:10.1006 / jagm.2000.1136.

[4] Cohen, J .; L. A. Rodrigues; F. Silva; R. Carmo; A. Guedes; E. P. Duarte Jr. (2011). "Gusfield'ın Kesme Ağacı Algoritmasının Paralel Uygulamaları". Bilgisayar Bilimlerinde Ders Notları (LNCS). 7016. Springer. 7016 (11th International Conference Algorithms and Architectures for Parallel Processing (ICA3PP)): 258-269. doi:10.1007/978-3-642-24650-0_22. ISBN 978-3-642-24649-4. ISSN 0302-9743.

[5] Hartvigsen, D .; Mardon, R. (1994). "Tüm çiftler minimum kesim problemi ve düzlemsel grafiklerde minimum döngü temel problemi". SIAM J. Ayrık Matematik. 7 (3): 403–418. doi:10.1137 / S0895480190177042..

[1]

[2]

[3]

[4]

[5]