Разбиение графа

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пример разбиения параллельной граф-схемы алгоритма логического управления. В составе блоков, отмеченных разными цветами, нет параллельных вершин

Разбиение графа на подграфы (англ. Graph partition) (иногда в литературе также употребляется термин разрезание графа[1]) — представление исходного графа в виде множества подмножеств вершин по определенным правилам. Обычно по условию задачи требуется, чтобы , то есть все вершины исходного графа должны быть распределены по подмножествам, причем . Обычно также дополнительно вводится требование ортогональности разбиения: , то есть одна и та же вершина не может входить в состав различных подмножеств. Иногда из множества возможных разбиений требуется выбрать одно, удовлетворяющее ограничениям и являющееся оптимальным (либо субоптимальным) по обозначенному критерию, либо доказать, что искомое разбиение не существует (ограничения противоречивы). Задача разбиения графа относится к классу NP-полных, верхняя оценка числа разбиений определяется числом Белла, однако при этом обычно не все возможные разбиения являются корректными (не нарушают ограничений), то есть оценка является завышенной. При значениях числа вершин графа более 15—20 получение оптимальных разбиений как правило невозможно за приемлемое время (иногда для этого используется метод ветвей и границ), поэтому на практике ограничиваются субоптимальными решениями, полученными с использованием эвристических алгоритмов.

Необходимость получения разбиения возникает при решении ряда задач:

  1. Задача раскраски графа — каждое множество вершин состоит из вершин одного цвета, причем вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса NP (критерий оптимальности — ).
  2. Задача определения числа и состава компонент связности графа.
  3. При проектировании топологии локальной сети её разбиение на широковещательные домены определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к файловым серверам, службам DHCP, WINS, DNS и т. д.), ограничения — число портов и пропускная способность коммутаторов, маршрутизаторов и каналов связи, а также стоимость).
  4. В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.[2]
  5. В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.[3][4][5][6]
  6. Представление графа в виде ярусно-параллельной формы или граф-схемы алгоритма в виде множества сечений (множества вершин в составе сечений могут быть неортогональными).
  7. Разбиение графа алгоритма на непересекающиеся подграфы с последующим их размещением в процессорных элементах или элементах в составе ПЛИС при реализации конвейерной обработки данных (балансировка нагрузки).[7][8]

Методы разбиения графа[9][править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.
  2. Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.
  3. Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.
  4. Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
  5. Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
  6. Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrucken: Lambert Academic Publishing, 2011 г. 292 с. ISBN 978-3-8433-1728-3
  7. Каляев И. А., Левин И. И., Семерников Е. А., Шмойлов В. И. Реконфигурируемые мультиконвейерные вычислительные структуры: 2-е издание. Ростов н/Д: изд-во ЮНЦ РАН, 2009. 344 с. ISBN 978-5-902982-61-6
  8. Каляев И. А., Левин И. И. Реконфигурируемые мультиконвейерные вычислительные системы для решения потоковых задач обработки информации и управления // Пленарные доклады 5-й международной конференции «Параллельные вычисления и задачи управления» (PACO’10). М.: ИПУ РАН, 2010 г. С. 23—37.
  9. INTUIT.ru: Курс: Теория и практика ..: Лекция № 10: Параллельные методы на графах