Планаризацией графа называется разбиение графа G(X,U) на m планарных суграфов (те же вершины, но некоторые ребра опущены) L1(X,Z1), L2(X,Z2)…Lm(X,Zm). Min m – толщина графа.
15. Раскраска графов
Раскраской называется разбиение множества вершин на подмножества таким образом, чтобы вершины внутри каждого из подмножеств были не смежными.
–
устойчивое внутреннее множество
Минимальное количество подмножеств, на которое граф разбивается при его раскраске, называется хроматическим числом. Различают точные и приближенные алгоритмы раскраски. NP-полный и NP-точный, для нее существуют только экспоненциально точные алгоритмы.
Алгоритм Вейсмана (использует метод Магу)
1. Метод Магу – построение всех максимальных внутренне устойчивых множеств графа.
2. Метод Петрика – выбор из всех множеств минимальное количество множеств, покрывающих все вершины.
Подробнее.
1. Для всех вершин:
–
количество вершин, смежных вершине 
.
2. Выбирается вершина с максимальным 
, и для нее записывается
выражение: Из графа удаляется вершина 
и
идентичные ей вершины. Из матрицы R удаляется строка и столбец, соответствующий . До тех пор, пока 
переходим к п.1
3. 
и далее
минимизация на основе булевой алгебры (тафталогия и поглощение)
, где 
– вершины, не вошедшие в j-терм.
(максимальное внутреннее устойчивое множество)
Метод Петрика
Метод используется для нахождения всех минимальных покрытий конституент единицы и позволяет получить все тупиковые ДНФ по импликантной матрице. Суть метода заключается в следующем. По импликантной матрице строится т.н. конъюнктивное представление мипликантной матрицы. Для этого все простые импликанты обозначаются разными буквами (обычно прописными латинскими). После этого, для каждого i-го столбца импликантной матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пересечение которых с i-м столбцом отмечено крестиком. Конъюнктивное представление импликантной матрицы образуется как конъюнкция построенных дизъюнкций для всех столбцов матрицы. К конъюнктивному представлению матрицы могут быть применены все соотношения булевой алгебры с целью его упрощения. После раскрытия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ (Дизъюнктивная нормальная форма).
16. Этапы компоновки, размещения элементов и трассировки межсоединений
Основные задачи конструкторского проектирования:
1. Компоновка.Распределение элементов низшего уровня иерархии по элементам высшего уровня иерархии. 2 постановки задачи: покрытие (библиотека элементов) и разрезание
2. Размещение на элементах высшего уровня иерархии
3. Трассировка.Реализация соединений на всех уровнях иерархии
4. Выпуск конструкторско-технологической документации
Алгоритм компоновки. Различают алгоритмы из множества программ: последовательные алгоритмы, итерационные, смешанные. Любой итерационный алгоритм включает следующие шаги:
Получение очередного варианта решения
Вычисление функции критерия
Выбор лучшего варианта
Срабатывание правила останова
Особенность: в любой момент есть решение и поэтому всегда можно прекратить …
Начальное решение получается либо последовательным решением, либо случайно, либо задает конструктор. Качество итерационного решения зависит от начального решения. Задача ставится следующим образом: G(X; U) разрезать на m частей => G1(X1; U1); G2(X2; U2) … Gm(Xm; Um) так, чтобы UXi =X UUi =U xi∩ xj =Ø (не пересекались). Ui =Uii U Uij
Необходимо минимизировать | Uij | - количество внешних связей пусков
А парных перестановок.
Берем G1 и G2. Для каждой вершины вычисляется αi.
αi – показывает, как изменится число внешних связей между двумя пусками, если i–ая вершина перейдет в другой кусок. Для каждой пары из разных пусков: bij – 2 вершины поменяются.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.