Разбиение графа: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Addbot (обсуждение | вклад) м Перемещение 3 интервики на Викиданные, d:q491370 |
Robiteria (обсуждение | вклад) м Разрешение значений с помощью бота: Коммутатор — изменение ссылок на Сетевой коммутатор; косметические изменения |
||
Строка 4:
Необходимость получения разбиения возникает при решении ряда задач:
# Задача [[Раскраска графа|раскраски графа]] — каждое множество вершин <math>V_i</math> состоит из вершин одного цвета, причем вершины одного цвета не имеют общих инцидентных рёбер. Обычно интересует отыскание минимальной раскраски, что в общем случае является задачей класса [[
# Задача определения числа и состава [[Компонента связности графа|компонент связности графа]].
# При проектировании топологии [[Локальная вычислительная сеть|локальной сети]] ее разбиение на [[Широковещательный домен|широковещательные домены]] определяется требованиями производительности (критерий оптимальности — объем передаваемого междоменного трафика при использовании различных серверов и сетевых служб (доступ к [[файловый сервер|файловым серверам]], службам [[DHCP]], [[WINS]], [[DNS]] и т. д.), ограничения — число портов и пропускная способность [[Сетевой коммутатор|коммутаторов]]
# В задаче трассировки межсоединений [[печатная плата|печатных плат]] или [[микросхема|микросхем]] необходимо разбиение исходной схемы на слои (каждый из которых представляет собой [[планарный граф]]). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов. <ref>Курейчик В. М., Глушань В. М., Щербаков Л. И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.</ref>
# В задаче разбиения [[граф-схема алгоритма|граф-схемы алгоритма]] на блоки с целью реализации на многопроцессорной системе или [[Система логического управления|логическом мультиконтроллере]]. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой. <ref>Баранов С. И., Журавина Л. Н., Песчанский В. А. Метод представления параллельных граф-схем алгоритмов совокупностями последовательных граф-схем // Автоматика и вычислительная техника. 1984. № 5. С. 74—81.</ref><ref>Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4</ref><ref>Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управлени при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5</ref><ref>Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. [[Саарбрюккен|Saarbrucken]]: [[VDM Publishing|Lambert Academic Publishing]], 2011 г. 292 с. ISBN 978-3-8433-1728-3</ref>
| |||