고모리후나무

조합 최적화에서 용량이 있는 무방향 그래프의 Gomory-Hu 트리는^[1] 그래프의 모든 s-t 쌍에 대한 최소 s-t 절단을 나타내는 가중치 트리입니다. Gomory–Hu 트리는 V - 1 최대 흐름 계산으로 구성할 수 있습니다. 그것은 랄프 E. 고모리와 T. C. Hu의 이름을 따서 지어졌습니다.

정의.

$G$ =${\displaystyle }$($,$ EG, $c$) ${\displaystyle$ G = (V_{G},E_{G},c)}를 각각 에지(u,v) {\displaystyle (u,v)}의 용량으로 하는 무방향 그래프라고 가정합니다.

${\displaystyle 각{}_{}}$, $t$∈ V G $displaystyle$ s,t\in V_{G}}에 대해 s-t 컷의 최소 용량을 λ st ${\displaystyle$ \$lambda$_{st}}로 표시합니다.

$T$ =${\displaystyle }$($,$ ET) {\$displaystyle$ T = ($V_{G$},E_{T}}를 트리라고 하고, 각 s에 대해 pst {\displaystyle P_{st}}, t ∈ VG {\displaystyle s,t\in V_{G}}에 의해 s-t 경로의 간선 집합을 나타냅니다.

그렇다면 T는 G의 Gomory–Hu 트리라고 하며, 만약 각 $s$에 ${\displaystyle {대하여}_{}}$ ${\displaystyle t}$∈ $VG {\displaystyles,t\$in V_{G}}

${\displaystyle \lambda _{st}=\min _{e\in P_{st}}c(S_{e},T_{e}),}$

어디에

1. $⊆$${\displaystyle \mathrm{T\_}}$${e}\subseteq V_{G}}$는 T $∖$ {e} ${\displaystyle$ T$\setminus$\{e\}의 두 연결된 구성 ${\displaystyle {요소}_{}}$이므로$,$ $Te$) ${\displaystyle ($S_{e},$T_{e}}$은(는) G에서 s-t 컷을$$ 형성합니다.
2. ${\displaystyle$$T_{e}}$은$({\displaystyle }$는${\displaystyle {}_{}}$ ${\displaystyle(S_{e})$의 용량입니다.$T_{e}}$를 G로 자릅니다$$.

알고리즘.

고모리-후 알고리즘

입력: 가중치가 부여된 무방향 $그래프$ G =$,$ $EG ), c$) {\displaystyle G = ((V_{G}, E_{G}),c)}

출력: 고모리-후 트리 $T$ = (${\displaystyle {VT}_{},}$ ${\displaystyle {ET}_{}{}_{}}$ ${\$displaystyle T = (V_{T},E_{T})}

1. ${\displaystyle {VT}_{}}$ =${\displaystyle }${${\displaystyle {VG}_{}\},}$ ET = ∅를 설정합니다. {\$displaystyle$ V_{$T}=\{V_{G}\},\ E_{T}=\emptyset .}$
2. X가 존재하는 경우 $X$ ≥ ${\displaystyle 2_{}}$가 있는 X ∈ V T${\displaystyle X\$in V_{T}}를 선택합니다. 그렇지 않으면 6단계로 이동합니다.
3. $\underset{}{{}_{}}$된 각 구성 요소 $C$ =${\displaystyle }$($,$ EC) ∈ T$$∖$$X, {\$displaystyle$C = ($V_${C},E_{C})\in T\setminus X,}에서 SC = ⋃ V T ∈ V. {\textstyle S_{C}=\bigcup _{v_{T}\in V_{C}v_{T}}입니다.

   $S$ =${\displaystyle }${ $SC$∣ $C가$T ∖ X}에서 $연결된 구성$ 요소라고 하자. {\displaystyle S=\{S_{C}\mid C{\text{는}}T\setminus X\}에서 연결된 구성 요소입니다.

   구성 요소를 수축하여 $G{\displaystyle {\text{'}}^{}}$ =$',$ EG'), c'), {\displaystyle G' = ((V_{G'}, E_{G'}), c'}를 형성합니다. 여기서 다음과 같습니다.

   $${\displaystyle {\begin{aligned}V_{G'}&=X\cup S\\[2pt]E_{G'}&=E_{G} _{X\times X}\cup \{(u,S_{C})\in X\times S\mid (u,v)\in E_{G}{\text{ for some }}v\in S_{C}\}\\[2pt]&\qquad \qquad \quad \!\cup \{(S_{C1},S_{C2})\in S\times S\mid (u,v)\in E_{G}{\text{ for some }}u\in S_{C1}{\text{ and }}v\in S_{C2}\}\end{aligned}}}$$

   

   ${\displaystyle$$V_{G'}\times V_{G'}\to$ R$^{+}$는 용량 함수로 다음과 같이 정의됩니다.

   $${\displaystyle {\aligned}&{\text{if}}\(u,S_{C})\in E_{G}_{X\times S:&c'(u,S_{C})=\!\!\sum _{\begin{smallmatrix}v\in S_{C}:\\(u,v)\in E_{G}\end{smallmatrix}}\!\!\!c(u,v)\\[4pt]&{\text{if }}\ (S_{C1},S_{C2})\in E_{G} _{S\times S}:&&c'(S_{C1},S_{C2})=\!\!\!\!\!\!\!\sum _{\begin{smallmatrix}(u,v)\in E_{G}:\\u\in S_{C1}\,\land \,v\in S_{C2}\end{smallmatrix}}\!\!\!\!\!c(u,v)\\[4pt]&{\text{otherwise}}:&&c'(u,v)=c(u,v)\end{aligned}}}$$

   

4. 두 꼭짓점 t ∈ X를 선택하고 G'에서 최소 s-t 절단(A', B')을 찾습니다.

   ${\displaystyle \underset{}{{}^{}}}$ $A$ =${\displaystyle \underset{}{{}_{}}}$⋃$$SC ∈ A' ∩ SSC) ∪ (A' ∩ X), {\displaystyle A={\Biggl(}\bigcup _{S_{C}\in A'\cap S}\!$\!S_{C}\!$${\Biggr )}\cup$(${\displaystyle \underset{}{{}^{}}}$$'\cap$ X$),\ }$ $B$ $=$${\displaystyle \underset{}{{}_{}}}$$⋃$$SC$$∈$ B' $∩$ SSC) $∪$ (B' $∩$ X). {\displaystyle B$=${\Biggl (}\bigcup _{S_{C}\in B'\cap S}\!$\!S_{C}\!$${\Biggr )}\cup (B'\cap X)}$

5. $V$ ${\displaystyle T_{}}$ =${\displaystyle }$($V$ T ∖ X) ∪ {A ∩ X, B ∩ X}. {\displaystyle V_{T}=(V_{T}\setminus X)\cup \{A\cap X,B\cap X\}를 설정합니다.

   각 $e$ = ($,$ Y) ∈ ET {\displaystyle e = (X, Y)\in E_{T}에 대해 다음을 수행합니다.

   1. $설정$ e${\displaystyle {\text{'}}^{}}$ =${\displaystyle }$(${\displaystyle A}$∩ X, Y) {\$displaystyle$e'= $($A\cap X,Y)} Y ⊂ A이면 {\displaystyle Y\subset A,} 그렇지 않으면 설정 e' = (B ∩ X,Y ) {\displaystyle e'= (B\cap X,Y)}
   2. ${\displaystyle {ET}_{}}$ =${\displaystyle }$(${\displaystyle {ET}_{}}$ ∖ {e$})$ ∪ {e'}을(를) 설정합니다. {\displaystyle E_{T}= (E_{$T}\setminus \{e\})\cup \{e'\}.}$
   3. $w{\displaystyle ({}^{}\text{'})}$ = w$).$ {\displaystyle w(e')= w(e)}를 설정합니다.

   ${\displaystyle {ET}_{}}$ = ${\displaystyle \mathrm{ET}}$ ∪${(A$ ∩ X, B ∩ X)}을(를) 설정합니다. {\displaystyle E_{T}=E_{T}\cup \{(A\cap X,\B\cap X)\}

   ${\displaystyle {}^{}}$ w${\displaystyle ((A}$∩${\displaystyle X}$, B ∩ ${\displaystyle X}$)${\displaystyle }$= c$'(A',$ B'). ${\displaystyle$ w((A\cap X, B\cap X)) = c'(A', B').}

   2단계로 이동합니다.

6. V_{T}에서 $각${v$}$$$∈ $V T$ {\displaystyle \{v\}\in V_{T}를 v로, 각 ({u}, {v}) ∈ ET {\displaystyle(\{u\},\{v\})\in E_{$T}$ by$$ (u, v). 출력 T.

분석.

capacity function c의 하위 모듈 특성을 사용하면,

그렇다면 G'의 최소 s-t 절단도 임의의 s, t ∈ X에 대하여 G의 최소 s-t 절단임을 알 수 있습니다.

${\displaystyle {모든}_{}}$(${\displaystyle P,}$ ${\displaystyle Q)}$ ∈ ET에 $대해${\displaystyle (P, Q)\in E_{T}} w (P, Q) = λ p q {\displaystyle w (P, Q)=\lambda _{pq}}에 대해 알고리즘 전체에 걸쳐 다음 보조정리를 사용함을 보여줍니다.

임의의 i, j, k in V,${\displaystyle {}_{}}$λ${\displaystyle }$ik ≥ ${\displaystyle min{}_{}}$(λ i j,$$λ$$j $k$) . ${\displaystyle \lambda$_{$ik$}\$geq$\min (\lambda _{ij},\lambda _{jk}).

보조정리는 출력 T가 Gomory-Hu Tree의 특성을 만족한다는 것을 보여주기 위해 다시 반복적으로 사용될 수 있습니다.

예

다음은 고모리를 시뮬레이션한 것입니다.후의 알고리즘, 어디서

1. 녹색 원은 T의 꼭짓점입니다.
2. 빨간색과 파란색 원은 G'의 꼭짓점입니다.
3. 회색 꼭짓점은 선택된 s와 t입니다.
4. 빨간색과 파란색 색상은 s-t 컷을 나타냅니다.
5. 점선 모서리는 s-t 절단 집합입니다.
6. A는 빨간색으로 동그라미를 친 꼭짓점 집합이고 B는 파란색으로 동그라미를 친 꼭짓점 집합입니다.

	G'	T
	1. Set VT = {VG} = { {0, 1, 2, 3, 4, 5} } and ET = ∅. 2. V에는 정점이 하나만 있으므로 X = V = {0, 1, 2, 3, 4, 5}를 선택합니다. X = 6 ≥ 2에 유의하십시오.
1.
	3. T\X = ∅이므로 수축이 없으므로 G' = G입니다. 4. = 1 및 t = 5를 선택합니다. 최소 s-t 컷(A', B')은 ({0, 1, 2, 4}, {3, 5})이고 c'(A', B') = 6입니다. Set A = {0, 1, 2, 4} and B = {3, 5}. 5. Set VT = (VT\X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3, 5} }. Set ET = { ({0, 1, 2, 4}, {3, 5}) }. Set 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}은(는) T\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, t = 5를 선택합니다. G'의 최소 s-t 컷(A', B')은 ({0, 1, 2, 4}, 3}, {5})이고 c'(A', B') = 8입니다. Set A = {0, 1, 2, 3, 4} and B = {5}. 5. Set VT = (VT\X) ∪ {A ∩ X, B ∩ X} = { {0, 1, 2, 4}, {3}, {5} }. Since (X, {0, 1, 2, 4}) ∈ ET and {0, 1, 2, 4} ⊂ A, replace it with (A ∩ X, Y) = ({3}, {0, 1, 2 ,4}). Set ET = { ({3}, {0, 1, 2 ,4}), ({3}, {5}) } with 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}은(는) T\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'(u,v) = c(u,v) for all u,v ∈ X. 4. s = 1, t = 2를 선택합니다. G'의 최소 s-t 컷(A', B')은 ({1, {3, 5, 4, {0, 2})이고, c'(A', B') = 6. Set A = {1, 3, 4, 5} and B = {0, 2}. 5. Set VT = (VT\X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1, 4}, {0, 2} }. (X, {3}) ∈ E와 {3} ⊂ A이므로 (A ∩ X, Y) =({1, 4}, {3})로 바꿉니다. Set ET = { ({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4}) } with 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}}이(가) T\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'(u,v) = c(u,v) for all u,v ∈ X. 4. = 1, t = 4를 선택합니다. G'의 최소 s-t 컷(A', B')은 ({1, {3, 5}, {{0, 2}, 4})이고 c'(A', B') = 7입니다. Set A = {1, 3, 5} and B = {0, 2, 4}. 5. Set VT = (VT\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})로 바꿉니다. Set ET = { ({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4}) } with 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}}이(가) T\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. s = 0, t = 2를 선택합니다. G'의 최소 s-t 컷(A', B')은 ({0}, {2, {1, 3, 4, 5})이고 c'(A', B') = 8입니다. Set A = {0} and B = {1, 2, 3 ,4 ,5}. 5. Set VT = (VT\X) ∪ {A ∩ X, B ∩ X} = { {3}, {5}, {1}, {4}, {0}, {2} }. (X, {4}) ∈ E와 {4} ⊂ B이므로 (B ∩ X, Y) = ({2, {4})로 바꿉니다. Set ET = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } with w(({2}, {4})) = w((X, {4})) = 6. w(({0}, {2})) = c'(A', B') = 8. 2단계로 이동합니다. 2. X ≥ 2가 있는 X ∈V는 존재하지 않습니다. 따라서 6단계로 이동합니다.
6.
	6. Replace VT = { {3}, {5}, {1}, {4}, {0}, {2} } by {3, 5, 1, 4, 0, 2}. Replace ET = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } by { (1, 3), (3, 5), (2, 4), (1, 4), (0, 2) }. 출력 T. 정확하게 V - 1 = 6 - 1 = 5배 min-cut 계산이 수행됩니다.

구현: 순차 및 병렬

Gusfield의 알고리즘을 사용하여 동일한 실행 시간-복잡성에서 정점 수축 없이 Gomory-Hu 트리를 찾을 수 있으므로 Gomory-Hu 트리를 구성하는 것이 간단해집니다.^[2]

앤드류 V. 골드버그와 K. Tsioutsiouliklis는 Gomory-Hu 알고리즘과 Gusfield 알고리즘을 구현하고 실험적 평가와 비교를 수행했습니다.^[3]

Cohen et al. 에서는 각각 OpenMP와 MPI를 사용하여 Gusfield의 알고리즘을 두 가지 병렬 구현한 결과를 보고합니다.^[4]

관련개념

평면 그래프에서 Gomory–Hu 트리는 Gomory–Hu 트리의 절단이 최소 중량 사이클 기반을 형성하는 이중 그래프의 사이클 모음과 이중이라는 점에서 최소 중량 사이클 기반과 이중입니다.^[5]

참고 항목

• 절단(그래프 이론)
• 최대 흐름 최소 절단 정리
• 최대 흐름 문제

참고문헌

• B. H. Korte, Jens Vygen (2008). "8.6 Gomory–Hu Trees". Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics, 21). Springer Berlin Heidelberg. pp. 180–186. ISBN 978-3-540-71844-4.