Рубрики

Дерево Гоморы-Ху | Комплект 1 (Введение)

Фон :
В потоковой сети первый разрез — это разрез, который требует, чтобы источник 's' и приемник 't' находились в разных подмножествах, и он состоит из ребер, идущих от стороны источника к стороне приемника. Мощность первого среза определяется суммой мощностей каждого края в наборе срезов. (Источник: Вики ). Учитывая две вершины, s и t, мы можем найти минимальный срез st, используя алгоритм максимального потока .

Поскольку существует всего O (n 2 ) возможных пар, на первый взгляд кажется, что будет всего O (n 2 ) общих минимальных значений st cut. Но когда мы используем дерево Гомори-Ху, мы увидим, что существует всего n-1 различных значений среза [Дерево с n вершинами имеет n-1 ребер]

Популярные графовые задачи, которые можно решить с помощью дерева Гомори-Ху:

  1. Для данного взвешенного и связного графа найдите минимальное сечение st для всех пар вершин. Или проблема, как найти минимум всех возможных минимальных сокращений st.
  2. Задача минимального K-разреза : найдите набор ребер с минимальным весом, удаление которых разделит график на k связанных компонентов. Это проблема NP-Hard, дерево Гомори-Ху дает приблизительное решение этой проблемы.

Что такое дерево Гомори-Ху ?
Дерево Гомори-Ху определено для потокового графа с краевой функцией емкости c. Дерево имеет тот же набор вершин, что и входной граф, и имеет n-1 (n — количество вершин) ребер. Функция краевой емкости c 'определяется с использованием следующих свойств:

Эквивалентное дерево потоков: для любой пары вершин s и t минимальный срез st в графе равен наименьшей пропускной способности ребер на пути между s и t в Tree.

Свойство обрезки: минимальное сечение в дереве также является минимальным срезом в Graph.G

Например, рассмотрим следующий граф и соответствующее дерево Гомори-Ху.

Поскольку в дереве с n узлами имеется n-1 ребер, мы можем заключить, что в сети потоков с n вершинами имеется не более n-1 разных значений потока.

Мы будем обсуждать строительство дерева в следующем посте.

Как решить вышеуказанные проблемы с помощью дерева Гомори-Ху?
Минимальное весовое ребро в дереве является минимальным из всех сечений.

Мы можем решить проблему k-cut, используя следующие шаги.
1) Построить дерево Гоморы-Ху.
2) Удалить k-1 минимальный вес (или самые легкие) края из дерева.
3) Вернуть объединение компонентов, полученных путем удаления краев.

Ниже схема иллюстрирует алгоритм выше.

Обратите внимание, что приведенное выше решение не всегда дает оптимальный результат, но оно гарантированно дает результаты в пределах (2-2 / k).

Ссылки:
https://www.corelab.ntua.gr/seminar/material/2008-2009/2008.10.20.Gomory-Hu%20trees%20and%20applications.slides.pdf
https://courses.engr.illinois.edu/cs598csc/sp2009/lectures/lecture_7.pdf
https://cseweb.ucsd.edu/classes/fa06/cse202/Gomory-Hu%20Tree.pdf

Эта статья предоставлена Dheeraj Gupta . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Дерево Гоморы-Ху | Комплект 1 (Введение)

0.00 (0%) 0 votes