Гомори-Ху ағашы - Gomory–Hu tree

Жылы комбинаторлық оңтайландыру, Гомори-Ху ағашы^[1] сыйымдылығы бар бағытталмаған графиктің салмағы бар ағаш бұл минималды білдіреді с-т барлығына арналған қысқартулар с-т графикадағы жұптар. Gomory-Ху ағашын | -де салуға боладыV | − 1 максималды ағын есептеулер.

Анықтама

Келіңіздер G = ((V_G, E_G), c) көмегімен бағытталмаған граф болуы керек c(сен,v) жиектің сыйымдылығы (сен,v) сәйкесінше.

Минималды сыйымдылығын белгілеңіз с-т кесу λ_ст әрқайсысы үшін с, т ∈ V_G.

Келіңіздер Т = (V_G, E_Т) ағаш болыңыз, оның жиектерінің жиілігін белгілеңіз с-т жол P_ст әрқайсысы үшін с, т ∈ V_G.

Содан кейін Т деп аталады Гомори-Ху ағашы туралы G, егер әрқайсысы үшін болса с, т ∈ V_G

λ_ст = мин_{e∈P_ст} c(S_e, Т_e),

қайда

S_e, Т_e ⊆ V_G екі байланысты компонент болып табылады Т∖{e}, және осылайша (S_e, Т_e) қалыптастыру с-т кесу G.
c(S_e, Т_e) - бұл кесудің сыйымдылығы G.

Алгоритм

Гомори-Ху алгоритмі

Кіріс: Бағытталмаған өлшенген график G = ((V_G, E_G), c)

Шығу: Гомори-ху ағашы Т = (V_Т, E_Т).

1. Орнатыңыз V_Т = {V_G} және E_Т = ∅.

2. Бірнешеуін таңдаңыз X∈V_Т бірге | X | If 2 болса X бар. Әйтпесе, 6-қадамға өтіңіз.

3. Әрбір қосылған компонент үшін C = (V_C, E_C) Т∖X. Келіңіздер S_C = ∪_{v_Т∈V_C} v_Т. Келіңіздер S = { S_C | C ішіндегі жалғанған компонент болып табылады Т∖X}.

Құрау үшін компоненттермен келісімшарт жасаңыз G' = ((V_{G '}, E_{G '}), c'), қайда

V_{G '} = X ∪ S.

E_{G '} = E_G|_{X × X} ∪ {(сен, S_C) ∈ X×S | (сен,v)∈E_G кейбіреулер үшін v∈S_C} ∪ {(S_C1, S_C2) × S ×S | (сен,v)∈E_G U∈ үшінS_C1 және v∈S_C2}.

c' : V_{G '}×V_{G '}→R⁺ ретінде анықталған сыйымдылық функциясы

егер (сен,S_C)∈E_G|_{X × S}, c'(сен,S_C) = Σ_{v∈S_C: (u, v) ∈E_G}c(сен,v),
егер (S_C1,S_C2)∈E_G|_{S × S}, c'(S_C1,S_C2) = Σ_{(u, v) ∈E_G: u∈S_C1∧v∈S_C2} c(сен,v),
c'(сен,v) = c(сен,v) басқаша.

4. Екі шыңды таңдаңыз с, т ∈ X және минимумды табыңыз с-т кесу (A',B') in G'.

Орнатыңыз A = (∪_{S_C∈A'∩S} S_C) ∪ (A' ∩ X) және B = (∪_{S_C∈B'∩S} S_C) ∪ (B' ∩ X).

5. Орнатыңыз V_Т = (V_Т∖X) ∪ {A ∩ X, B ∩ X}.

Әрқайсысы үшін e = (X, Y) ∈ E_Т істеу

Егер Y ⊂ A, орнатылған e' = (A ∩ X, Y), басқасы орнатылды e' = (B ∩ X, Y).

Орнатыңыз E_Т = (E_Т∖{e}) ∪ {e'} және w(e') = w(e).

Орнатыңыз E_Т = E_Т ∪ {(A∩X, B∩X)}.

Орнатыңыз w((A∩X, B∩X)) = c'(A', B').

2-қадамға өтіңіз.

6. Әрқайсысын ауыстырыңыз {v} ∈ V_Т арқылы v және әрқайсысы ({сен},{v}) ∈ E_Т арқылы (сен,v). Шығу Т.

Талдау

Пайдалану модульдік сыйымдылық функциясының қасиеті c, біреуінде бар

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

Сонда оны минималды деп көрсетуге болады с-т кесу G'сонымен қатар минимум с-т кесу G кез келген үшін с, т ∈ X.

Мұны бәріне көрсету үшін (P, Q) ∈ E_Т, w(P,Q) = λ_pq кейбіреулер үшін б ∈ P, q ∈ Q алгоритм барысында келесі Лемманы қолданады,

Кез келген үшін мен, j, к жылы V_G, λ_ик ≥ мин (λ.)_иж, λ_jk).

Лемманы шығуын көрсету үшін бірнеше рет қолдануға болады Т Gomory-Hu ағашының қасиеттерін қанағаттандырады.

Мысал

Төменде Gomory-Ху алгоритмін модельдеу келтірілген, мұндағы

жасыл шеңберлер - бұл шыңдар Т.
қызыл және көк шеңберлер - бұл шыңдар G'.
сұр шыңдар таңдалған с және т.
қызыл және көк бояу с-т кесу.
үзік-үзік шеттері с-т кесілген жиынтық.
A - шеңбердің шыңдарының жиынтығы қызыл және B - шеңбердің шыңдарының жиынтығы көк.

	G'	Т

	1. Орнатыңыз V_Т = {V_G} = {{0, 1, 2, 3, 4, 5}} және E_Т = ∅. 2. бастап V_Т тек бір шыңы бар, таңдаңыз X = V_G = {0, 1, 2, 3, 4, 5}. Назар аударыңыз \| X \| = 6 ≥ 2.
1.
	3. бастап Т∖X = ∅, онда ешқандай қысылу болмайды, сондықтан G' = G. 4. таңдаңыз с = 1 және т = 5. Минимум с-т кесу (A', B') - ({0, 1, 2, 4}, {3, 5}) -мен c'(A', B') = 6. Орнатыңыз A = {0, 1, 2, 4} және B = {3, 5}. 5. Орнатыңыз V_Т = (V_Т∖X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3, 5} }. Орнатыңыз E_Т = { ({0, 1, 2, 4}, {3, 5}) }. Орнатыңыз w( ({0, 1, 2, 4}, {3, 5}) ) = c'(A', B') = 6. 2-қадамға өтіңіз. 2. таңдаңыз X = {3, 5}. Назар аударыңыз \| X \| = 2 ≥ 2.
2.
	3. {0, 1, 2, 4} - қосылған компонент Т∖X және осылайша S = { {0, 1, 2, 4} }. {0, 1, 2, 4} келісімшарт жасасуға G', қайда 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. таңдаңыз с = 3, т = 5. Минимум с-т кесу (A', B') in G'({{0, 1, 2, 4}, 3}, {5}) мәнімен бірге c'(A', B') = 8. Орнатыңыз A = {0, 1, 2, 3, 4} және B = {5}. 5. Орнатыңыз V_Т = (V_Т∖X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3}, {5} }. Бастап (X, {0, 1, 2, 4}) ∈ E_Т және {0, 1, 2, 4} ⊂ A, оны (A ∩ X, Y) = ({3}, {0, 1, 2 ,4}). Орнатыңыз E_Т = {({3}, {0, 1, 2, 4}), ({3}, {5})} бірге w(({3}, {0, 1, 2 ,4})) = w((X, {0, 1, 2, 4})) = 6. w(({3}, {5})) = c'(A', B') = 8. 2-қадамға өтіңіз. 2. таңдаңыз X = {0, 1, 2, 4}. Назар аударыңыз \| X \| = 4 ≥ 2.
3.
	3. {{3}, {5}} - қосылған компонент Т∖X және осылайша S = { {3, 5} }. Келісімшарт {3, 5} G', қайда c'( (1, {3, 5}) ) = c( (1, 3) ) = 3. c'( (4, {3, 5}) ) = c( (4, 3) ) + c( (4, 5) ) = 3. c'(сен,v) = c(сен,v) барлығына сен,v ∈ X. 4. таңдаңыз с = 1, т = 2. Минимум с-т кесу (A', B') in G'({1, {3, 5}, 4}, {0, 2}) -мен c'(A', B') = 6. Орнатыңыз A = {1, 3, 4, 5} және B = {0, 2}. 5. Орнатыңыз V_Т = (V_Т∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1, 4}, {0, 2} }. Бастап (X, {3}) ∈ E_Т және {3} ⊂ A, оны (A ∩ X, Y) = ({1, 4}, {3}). Орнатыңыз E_Т = {({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4})} бірге w(({1, 4}, {3})) = w((X, {3})) = 6. w(({0, 2}, {1, 4})) = c'(A', B') = 6. 2-қадамға өтіңіз. 2. таңдаңыз X = {1, 4}. Назар аударыңыз \| X \| = 2 ≥ 2.
4.
	3. {{3}, {5}}, {{0, 2}} - қосылған компоненттер Т∖X және осылайша S = { {0, 2}, {3, 5} } Келісімшарт жасасу үшін {0, 2} және {3, 5} G', қайда 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'(сен,v) = c(сен,v) барлығына сен,v ∈ X. 4. таңдаңыз с = 1, т = 4. Минимум с-т кесу (A', B') in G'({1, {3, 5}}, {{0, 2}, 4}) с c'(A', B') = 7. Орнатыңыз A = {1, 3, 5} және B = {0, 2, 4}. 5. Орнатыңыз V_Т = (V_Т∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {0, 2}, {1}, {4} }. Бастап (X, {3}) ∈ E_Т және {3} ⊂ A, оны (A ∩ X, Y) = ({1}, {3}). Бастап (X, {0, 2}) ∈ E_Т және {0, 2} ⊂ B, оны (B ∩ X, Y) = ({4}, {0, 2}). Орнатыңыз E_Т = {({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'(A', B') = 7. 2-қадамға өтіңіз. 2. таңдаңыз X = {0, 2}. Назар аударыңыз \| X \| = 2 ≥ 2.
5.
	3. {{1}, {3}, {4}, {5}} - қосылған компонент Т∖X және осылайша S = { {1, 3, 4, 5} }. Келісімшарт {1, 3, 4, 5} G', қайда 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. таңдаңыз с = 0, т = 2. Минимум с-т кесу (A', B') in G'({0}, {2, {1, 3, 4, 5}}) - мен c'(A', B') = 8. Орнатыңыз A = {0} және B = {1, 2, 3 ,4 ,5}. 5. Орнатыңыз V_Т = (V_Т∖X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1}, {4}, {0}, {2} }. Бастап (X, {4}) ∈ E_Т және {4} ⊂ B, оны (B ∩ X, Y) = ({2}, {4}). Орнатыңыз E_Т = {({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) ) бірге w(({2}, {4})) = w((X, {4})) = 6. w(({0}, {2})) = c'(A', B') = 8. 2-қадамға өтіңіз. 2. Ол жоқ X∈V_Т бірге \| X \| ≥ 2. Демек, 6-қадамға өтіңіз.
6.
	6. Ауыстыру V_Т = {{3}, {5}, {1}, {4}, {0}, {2}} - {3, 5, 1, 4, 0, 2}. Ауыстыру E_Т = {({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) )} бойынша {(1, 3), (3, 5), (2, 4), (1, 4), (0, 2)}. Шығу Т. Дәл осы \| екенін ескеріңізV \| - 1 = 6 - 1 = 5 рет минималды есептеулер орындалады.

Іске асыру: дәйекті және параллель

Гусфилд алгоритмімен Gomory-Ху ағашын бірдей уақыттық күрделілікте кез-келген шыңы жиырылусыз табуға болады, бұл Gomory-Hu ағашын салуды жеңілдетеді.^[2]

Эндрю В.Голдберг және К.Циутсиуликлис Гомори-Ху алгоритмі мен Гусфилд алгоритмін іске асырды және эксперименталды бағалау мен салыстыруды жүзеге асырды.^[3]

Коэн және басқалар. сәйкесінше Гусфилд алгоритмінің OpenMP және MPI қолдана отырып екі параллельді іске асыруы туралы есеп.^[4]

Байланысты ұғымдар

Жылы жазықтық графиктер, Гомори-Ху ағашы ең төменгі салмаққа қосарланған цикл негізі, Гомори-Ху ағашының кесінділері циклдар жиынтығына қосарланған деген мағынада қос сызба минималды салмақ циклінің негізін құрайтын.^[5]

Сондай-ақ қараңыз

Пайдаланылған әдебиеттер

^ Гомори, Р.Э.; Ху, Т.С (1961). «Көп терминалды желі ағындары». Өнеркәсіптік және қолданбалы математика қоғамының журналы. 9 (4): 551–570. дои:10.1137/0109047.
^ Гусфилд, Дэн (1990). «Барлық жұптардың желілік ағындарын талдаудың өте қарапайым әдістері». SIAM J. Comput. 19 (1): 143–155. дои:10.1137/0219009.
^ Голдберг, А.В .; Tsioutsiouliklis, K. (2001). «Ағаш алгоритмдерін кесу: эксперименттік зерттеу». Алгоритмдер журналы. 38 (1): 51–83. дои:10.1006 / jagm.2000.1136.
^ Коэн Дж .; L. A. Rodriges; Ф. Сильва; Р. Кармо; A. Guedes; Е.П. Дуарте кіші (2011). «Гусфилдтің кесілген ағаш алгоритмінің параллельді орындалуы». Информатикадағы дәрістер (LNCS). 7016. Шпрингер. 7016 (Параллельді өңдеуге арналған 11-ші халықаралық конференция алгоритмдері мен сәулеттері (ICA3PP)): 258–269. дои:10.1007/978-3-642-24650-0_22. ISBN 978-3-642-24649-4. ISSN 0302-9743.
^ Хартвигсен, Д .; Мардон, Р. (1994). «Пландық графиктердегі мин-кесу есебі және минималды цикл есебі». SIAM J. Дискретті математика. 7 (3): 403–418. дои:10.1137 / S0895480190177042..

Б. Х. Корте, Дженс Виген (2008). «8.6 Гомори-ху ағаштары». Комбинаторлық оңтайландыру: теория және алгоритмдер (алгоритмдер және комбинаторика, 21). Springer Berlin Heidelberg. бет.180 –186. ISBN 978-3-540-71844-4.

[1] Гомори, Р.Э.; Ху, Т.С (1961). «Көп терминалды желі ағындары». Өнеркәсіптік және қолданбалы математика қоғамының журналы. 9 (4): 551–570. дои:10.1137/0109047.

[2] Гусфилд, Дэн (1990). «Барлық жұптардың желілік ағындарын талдаудың өте қарапайым әдістері». SIAM J. Comput. 19 (1): 143–155. дои:10.1137/0219009.

[3] Голдберг, А.В .; Tsioutsiouliklis, K. (2001). «Ағаш алгоритмдерін кесу: эксперименттік зерттеу». Алгоритмдер журналы. 38 (1): 51–83. дои:10.1006 / jagm.2000.1136.

[4] Коэн Дж .; L. A. Rodriges; Ф. Сильва; Р. Кармо; A. Guedes; Е.П. Дуарте кіші (2011). «Гусфилдтің кесілген ағаш алгоритмінің параллельді орындалуы». Информатикадағы дәрістер (LNCS). 7016. Шпрингер. 7016 (Параллельді өңдеуге арналған 11-ші халықаралық конференция алгоритмдері мен сәулеттері (ICA3PP)): 258–269. дои:10.1007/978-3-642-24650-0_22. ISBN 978-3-642-24649-4. ISSN 0302-9743.

[5] Хартвигсен, Д .; Мардон, Р. (1994). «Пландық графиктердегі мин-кесу есебі және минималды цикл есебі». SIAM J. Дискретті математика. 7 (3): 403–418. дои:10.1137 / S0895480190177042..

[1]

[2]

[3]

[4]

[5]