Дерево Гомори-Ху

В комбинаторной оптимизации дерево Гомори – Ху ^{[ 1 ]} неориентированного графа с пропускными способностями — это взвешенное дерево , которое представляет минимальные s — t разрезы для всех пар s — t в графе. Дерево Гомори–Ху можно построить в $| В | - 1$ расчет максимального расхода . Он назван в честь Ральфа Э. Гомори и TC Hu .

Определение

Позволять $G=(V_{G},E_{G},c)$ быть неориентированным графом с $c(u,v)$ является емкостью края $(u,v)$ соответственно.

Обозначим минимальную пропускную способность сечения

s

-

t

через

\lambda _{st}

для каждого

s,t\in V_{G}

.

Позволять

T=(V_{G},E_{T})

быть деревом, и обозначать множество ребер в

пути s

-

t

через

P_{st}

для каждого

s,t\in V_{G}

.

Тогда $T$ называется деревом Гомори–Ху группы $G$ , если для каждого $s,t\in V_{G}$

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

где

$S_{e},T_{e}\subseteq V_{G}$ являются двумя связными компонентами $T\setminus \{e\}$ , и таким образом $(S_{e},T_{e})$ образует $s$ - $t$ в $G.$ разрез
$c(S_{e},T_{e})$ это емкость $(S_{e},T_{e})$ в $G.$ вырезать

Алгоритм

Алгоритм Гомори – Ху

Входные данные : взвешенный неориентированный граф.

G=((V_{G},E_{G}),c)

Продукт : Дерево Гомори–Ху.

T=(V_{T},E_{T}).

Набор $V_{T}=\{V_{G}\},\ E_{T}=\emptyset .$
Выберите несколько $X\in V_{T}$ с $| Х | \geq 2,$ если такой $X$ существует. В противном случае перейдите к шагу 6.
Для каждого связного компонента $C=(V_{C},E_{C})\in T\setminus X,$ позволять ${\textstyle S_{C}=\bigcup _{v_{T}\in V_{C}}v_{T}.}$
Позволять $S=\{S_{C}\mid C{\text{ is a connected component in }}T\setminus X\}.$

Сожмите компоненты, чтобы сформировать $G'=((V_{G'},E_{G'}),c'),$ где: ${\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}}$
$c':V_{G'}\times V_{G'}\to R^{+}$ – функция емкости, определяемая как: ${\begin{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}}$
Выберите две вершины $s, t \in X$ и найдите минимальный $s - t$ разрез $(A', B')$ в $G'$ .
Набор $A={\Biggl (}\bigcup _{S_{C}\in A'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (A'\cap X),\$ $B={\Biggl (}\bigcup _{S_{C}\in B'\cap S}\!\!\!S_{C}\!{\Biggr )}\cup (B'\cap X).$
Набор $V_{T}=(V_{T}\setminus X)\cup \{A\cap X,B\cap X\}.$ $V_{T}=(V_{T}\setminus X)\чашка \{A\cap X, B\cap X\}.$
Для каждого $e=(X,Y)\in E_{T}$ $e=(X,Y)\in E_{T}$ делать:
1. Набор $e'=(A\cap X,Y)$ если $Y\subset A,$ в противном случае установить $e'=(B\cap X,Y).$
2. Набор $E_{T}=(E_{T}\setminus \{e\})\cup \{e'\}.$
3. Набор $w(e')=w(e).$
Набор $E_{T}=E_{T}\cup \{(A\cap X,\ B\cap X)\}.$

Набор $w((A\cap X,B\cap X))=c'(A',B').$

Перейдите к шагу 2.
Замените каждый $\{v\}\in V_{T}$ по $v$ и каждый $(\{u\},\{v\})\in E_{T}$ по $(ты, v)$ . Выход $Т.$

Анализ

Используя субмодулярное свойство функции емкости $c$ , имеем $c(X)+c(Y)\geq c(X\cap Y)+c(X\cup Y).$ Тогда можно показать, что минимальный $- t разрез$ в $G'$ также является минимальным $s - t$ разрезом в $G$ для любых $s, t \in X.$ s

Чтобы показать это всем $(P,Q)\in E_{T},$ $w(P,Q)=\lambda _{pq}$ для некоторых $p \in P$ , $q \in Q$ на протяжении всего алгоритма используется следующая лемма:

Для любых

i, j, k

в

V G

,

\lambda _{ik}\geq \min(\lambda _{ij},\lambda _{jk}).

Лемму можно использовать снова и снова, чтобы показать, что выходной сигнал $T$ удовлетворяет свойствам дерева Гомори – Ху.

Пример

Ниже приводится моделирование алгоритма Гомори – Ху, где

зеленые кружки — вершины T .
красные и синие кружки — вершины в G '.
серые вершины — выбранные s и t .
красный и синий цвета представляют собой разрез s - t .
пунктирные это вырезов края — набор .
A — это набор вершин, обведенных красным , а B — набор вершин, обведенных синим .

	Г '	Т

	1. Положим V _T = { V _G } = { {0, 1, 2, 3, 4, 5} } и E _T = ∅. 2. Поскольку VT _. имеет только одну вершину, выберем X = V _G = {0, 1, 2, 3, 4, 5} Обратите внимание, что \| Х \| = 6 ≥ 2.
1.
	3. Поскольку T \ X = ∅, сжатия нет и, следовательно, ' = G. G 4. Выберите s = 1 и t = 5. Минимальный s - t разрез ( A ', B ') равен ({0, 1, 2, 4}, {3, 5}) с c '( A ', B ') = 6. Установите A = {0, 1, 2, 4} и B = {3, 5}. 5. Положим V _T = ( V _T \ X ) ∪ { A ∩ X , B ∩ X } = { {0, 1, 2, 4}, {3, 5} }. Установите E _T = { ({0, 1, 2, 4}, {3, 5}) }. Положим w (({0, 1, 2, 4}, {3, 5})) = c '( A ', B ') = 6. Перейдите к шагу 2. 2. Выберите X = {3, 5}. Обратите внимание, что \| Х \| = 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. с '( (5, {0, 1, 2, 4})) = с ( (5, 4)) = 2. с '( (3, 5)) = с ( (3, 5) ) = 6. 4. Выберите s = 3, t = 5. Минимальный s - t разрез ( A ', B ') в G ' равен ( {{0, 1, 2, 4}, 3}, {5}) с c ' ( А ', В ') = 8. Установите A = {0, 1, 2, 3, 4} и B = {5}. 5. Положим V _T = ( V _T \ X ) ∪ { A ∩ X , B ∩ X } = { {0, 1, 2, 4}, {3}, {5} }. Поскольку ( X , {0, 1, 2, 4}) ∈ E _T и {0, 1, 2, 4} ⊂ A , замените его на ( A ∩ X , Y ) = ({3}, {0, 1 , 2 ,4}). Установите E _T = { ({3}, {0, 1, 2, 4}), ({3}, {5}) } с ш (({3}, {0, 1, 2, 4})) = ш (( X , {0, 1, 2, 4})) = 6. w (({3}, {5})) = c '( A ', B ') = 8. Перейдите к шагу 2. 2. Выберите X = {0, 1, 2, 4}. Обратите внимание, что \| Х \| = 4 ≥ 2.
3.
	3. { {3}, {5} } — компонента связности в T \ X и, следовательно, S = { {3, 5} }. Контракт {3, 5} образует G ', где с '( (1, {3, 5}) ) = с ( (1, 3) ) = 3. c '( (4, {3, 5})) = c ( (4, 3) ) + c ( (4, 5) ) = 3. c '( ты , v ) знак равно c ( ты , v ) для всех ты , v ∈ X . 4. Выберите s = 1, t = 2. Минимальный s - t разрез ( A ', B ') в G ' равен ( {1, {3, 5}, 4}, {0, 2} ) с c ' ( А ', В ') = 6. Установите A = {1, 3, 4, 5} и B = {0, 2}. 5. Положим V _T = ( V _T \ X ) ∪ { A ∩ X , B ∩ X } = { {3}, {5}, {1, 4}, {0, 2} }. Поскольку ( X , {3}) ∈ E _T и {3} ⊂ A , замените его на ( A ∩ X , Y ) = ({1, 4}, {3}). Установите E _T = { ({1, 4}, {3}), ({3}, {5}), ({0, 2}, {1, 4}) } с ш (({1, 4}, {3})) = ш (( X , {3})) = 6. w (({0, 2}, {1, 4})) = c '( A ', B ') = 6. Перейдите к шагу 2. 2. Выберите X = {1, 4}. Обратите внимание, что \| Х \| = 2 ≥ 2.
4.
	3. { {3}, {5} }, { {0, 2} } — компоненты связности в T \ X и, следовательно, S = { {0, 2}, {3, 5} } Свяжите {0, 2} и {3, 5}, чтобы сформировать G ', где с '( (1, {3, 5}) ) = с ( (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. с '( (4, {0, 2})) = с ( (4, 2) ) = 4. c '( ты , v ) знак равно c ( ты , v ) для всех ты , v ∈ X . 4. Выберите s = 1, t = 4. Минимальный s - t разрез ( A ', B ') в G ' равен ( {1, {3, 5}}, {{0, 2}, 4}) с с '( А ', В ') = 7. Установите A = {1, 3, 5} и B = {0, 2, 4}. 5. Положим V _T = ( V _T \ X ) ∪ { A ∩ X , B ∩ X } = { {3}, {5}, {0, 2}, {1}, {4} }. Поскольку ( X , {3}) ∈ E _T и {3} ⊂ A , замените его на ( A ∩ X , Y ) = ({1}, {3}). Поскольку ( X , {0, 2}) ∈ ET _{) = ({4} ,} и {0, 2} ⊂ B , замените его на ( B ∩ X , Y {0, 2}). Установите E _T = { ({1}, {3}), ({3}, {5}), ({4}, {0, 2}), ({1}, {4}) } с ш (({1}, {3})) = ш (( X , {3})) = 6. ш (({4}, {0, 2})) = ш (( X , {0, 2})) = 6. w (({1}, {4})) = c '( A ', B ') = 7. Перейдите к шагу 2. 2. Выберите X = {0, 2}. Обратите внимание, что \| Х \| = 2 ≥ 2.
5.
	3. { {1}, {3}, {4}, {5} } — компонента связности в T \ X и, следовательно, S = { {1, 3, 4, 5} }. Контракт {1, 3, 4, 5} образует G ', где с '( (0, {1, 3, 4, 5})) = с ( (0, 1) ) = 1. с '( (2, {1, 3, 4, 5})) = с ( (2, 1) ) + с ( (2, 4) ) = 5. с '( (0, 2)) = с ( (0, 2) ) = 7. 4. Выберите s = 0, t = 2. Минимальный s - t разрез ( A ', B ') в G ' равен ( {0}, {2, {1, 3, 4, 5}} ) с c ' ( А ', В ') = 8. Установите A = {0} и B = {1, 2, 3, 4, 5}. 5. Положим V _T = ( V _T \ X ) ∪ { A ∩ X , B ∩ X } = { {3}, {5}, {1}, {4}, {0}, {2} }. Поскольку ( X , {4}) ∈ ET _{) = ({2} ,} и {4} ⊂ B , замените его на ( B ∩ X , Y {4}). Установить E _T = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } с ш (({2}, {4})) = ш (( X , {4})) = 6. w (({0}, {2})) = c '( A ', B ') = 8. Перейдите к шагу 2. 2. Не существует X ∈ V _T такого, что \| Х \| ≥ 2. Следовательно, переходим к шагу 6.
6.
	6. Замените V _T = { {3}, {5}, {1}, {4}, {0}, {2} } на {3, 5, 1, 4, 0, 2}. Замените E _T = { ({1}, {3}), ({3}, {5}), ({2}, {4}), ({1}, {4}), ({0}, {2}) } на { (1, 3), (3, 5), (2, 4), (1, 4), (0, 2) }. Выход Т. Обратите внимание, что именно \| В \| − 1 = 6 − 1 = 5 раз выполняется вычисление минимального сокращения.

Реализации: последовательные и параллельные

Алгоритм Гасфилда можно использовать для поиска дерева Гомори – Ху без какого-либо сжатия вершин при той же сложности времени выполнения , что упрощает реализацию построения дерева Гомори – Ху. ^{[ 2 ]}

Эндрю В. Голдберг и К. Циуциуликлис реализовали алгоритм Гомори-Ху и алгоритм Гасфилда, а также выполнили экспериментальную оценку и сравнение. ^{[ 3 ]}

Коэн и др. сообщают о результатах двух параллельных реализаций алгоритма Гасфилда с использованием OpenMP и MPI соответственно. ^{[ 4 ]}

Связанные понятия

В плоских графах дерево Гомори-Ху двойственно базису цикла минимального веса в том смысле, что разрезы дерева Гомори-Ху двойственны набору циклов в двойственном графе, которые образуют базис цикла минимального веса. ^{[ 5 ]}

См. также

Ссылки

^ Гомори, RE ; Ху, ТК (1961). «Многотерминальные сетевые потоки». Журнал Общества промышленной и прикладной математики . 9 (4): 551–570. дои : 10.1137/0109047 .
^ Гасфилд, Дэн (1990). «Очень простые методы анализа потоков в сети для всех пар». СИАМ Дж. Компьютер . 19 (1): 143–155. дои : 10.1137/0219009 .
^ Гольдберг А.В.; Циуциуликлис, К. (2001). «Алгоритмы обрезки дерева: экспериментальное исследование». Журнал алгоритмов . 38 (1): 51–83. дои : 10.1006/jagm.2000.1136 .
^ Коэн, Хайме; Родригес, Луис А.; Сильва, Фабиано; Кармо, Ренато; Гедес, Андре Луис Пирес; Дуарте-младший, Элиас П. (2011). «Параллельные реализации алгоритма разрезания дерева Гасфилда». В Сян, Ян; Куццокрея, Альфредо; Хоббс, Майкл; Чжоу, Ванлей (ред.). Алгоритмы и архитектуры для параллельной обработки — 11-я Международная конференция, ICA3PP, Мельбурн, Австралия, 24–26 октября 2011 г., Материалы, Часть I. Конспекты лекций по информатике. Том. 7016. Спрингер. стр. 258–269. дои : 10.1007/978-3-642-24650-0_22 . {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Хартвигсен, Д.; Мардон, Р. (1994). «Задача о минимальном разрезе для всех пар и задача о базисе минимального цикла на плоских графах». СИАМ Дж. Дискретная математика . 7 (3): 403–418. дои : 10.1137/S0895480190177042 . .

Б. Х. Корте, Йенс Виген (2008). «8.6 Деревья Гомори – Ху». Комбинаторная оптимизация: теория и алгоритмы (Алгоритмы и комбинаторика, 21) . Шпрингер Берлин Гейдельберг. стр. 180–186 . ISBN 978-3-540-71844-4 .

[1] Гомори, RE ; Ху, ТК (1961). «Многотерминальные сетевые потоки». Журнал Общества промышленной и прикладной математики . 9 (4): 551–570. дои : 10.1137/0109047 .

[2] Гасфилд, Дэн (1990). «Очень простые методы анализа потоков в сети для всех пар». СИАМ Дж. Компьютер . 19 (1): 143–155. дои : 10.1137/0219009 .

[3] Гольдберг А.В.; Циуциуликлис, К. (2001). «Алгоритмы обрезки дерева: экспериментальное исследование». Журнал алгоритмов . 38 (1): 51–83. дои : 10.1006/jagm.2000.1136 .

[4] Коэн, Хайме; Родригес, Луис А.; Сильва, Фабиано; Кармо, Ренато; Гедес, Андре Луис Пирес; Дуарте-младший, Элиас П. (2011). «Параллельные реализации алгоритма разрезания дерева Гасфилда». В Сян, Ян; Куццокрея, Альфредо; Хоббс, Майкл; Чжоу, Ванлей (ред.). Алгоритмы и архитектуры для параллельной обработки — 11-я Международная конференция, ICA3PP, Мельбурн, Австралия, 24–26 октября 2011 г., Материалы, Часть I. Конспекты лекций по информатике. Том. 7016. Спрингер. стр. 258–269. дои : 10.1007/978-3-642-24650-0_22 . {{cite conference}}: CS1 maint: несколько имен: список авторов ( ссылка )

[5] Хартвигсен, Д.; Мардон, Р. (1994). «Задача о минимальном разрезе для всех пар и задача о базисе минимального цикла на плоских графах». СИАМ Дж. Дискретная математика . 7 (3): 403–418. дои : 10.1137/S0895480190177042 . .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]