Русская Википедия:Разбиение графа
Разбиение графа на подграфы (Шаблон:Lang-en) (иногда в литературе также употребляется термин разрезание графа[1]) — представление исходного графа <math>G=\left \langle A, V \right \rangle</math> в виде множества подмножеств вершин <math>\mathrm{Sep}~A = \left \{ A_1, A_2, ..., A_n \right \}, A_i \subseteq A</math> по определенным правилам. Обычно по условию задачи требуется, чтобы <math>\bigcup_{i=1}^{n} A_i = A</math>, то есть все вершины исходного графа должны быть распределены по подмножествам, причём <math>A_i \neq \varnothing</math>. Обычно также дополнительно вводится требование ортогональности разбиения: <math>\forall i \neq j~ A_i \cap A_j = \varnothing</math>, то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа <math>N=\left| A \right|</math> более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов.
Необходимость получения разбиения возникает при решении ряда задач:
- Задача раскраски графа — каждое множество вершин <math>V_i</math> состоит из вершин одного цвета, причём вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса NP (критерий оптимальности — <math>n \rightarrow \min</math>).
- Задача определения числа и состава компонент связности графа.
- При проектировании топологии локальной сети её разбиение на широковещательные домены определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к файловым серверам, службам DHCP, WINS, DNS и т. д.), ограничения — число портов и пропускная способность коммутаторов, маршрутизаторов и каналов связи, а также стоимость).
- В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.[2]
- В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.[3][4][5][6]
- Представление графа в виде ярусно-параллельной формы или граф-схемы алгоритма в виде множества сечений (множества вершин в составе сечений могут быть неортогональными).
- Разбиение графа алгоритма на непересекающиеся подграфы с последующим их размещением в процессорных элементах или элементах в составе ПЛИС при реализации конвейерной обработки данных (балансировка нагрузки).[7][8]
Методы разбиения графа[9]
- Покоординатное разбиение
- Рекурсивный инерционный метод деления пополам
- Деление сети с использованием кривых Пеано
- Деление с учётом связности (по сути, поиск в ширину)
- Шаблон:Нп1
См. также
Примечания
- ↑ Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.
- ↑ Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
- ↑ Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.
- ↑ Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
- ↑ Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
- ↑ Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrucken: Lambert Academic Publishing, 2011 г. 292 с. ISBN 978-3-8433-1728-3
- ↑ Каляев И. А., Левин И. И., Семерников Е. А., Шмойлов В. И. Реконфигурируемые мультиконвейерные вычислительные структуры: 2-е издание. Ростов н/Д: изд-во ЮНЦ РАН, 2009. 344 с. ISBN 978-5-902982-61-6
- ↑ Каляев И. А., Левин И. И. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач обработки информации и управления // Пленарные доклады 5-й международной конференции «Параллельные вычисления и задачи управления» (PACO’10). М.: ИПУ РАН, 2010 г. С. 23—37.
- ↑ INTUIT.ru: Курс: Теория и практика ..: Лекция № 10: Параллельные методы на графахШаблон:Недоступная ссылка
