Размещение элементов по коммутационной плате и распределение цепей по выводам узла

Федеральное агентство по образованию РФ

Государственное образовательное учреждение высшего профессионального образования

«Владимирский государственный университет»

Кафедра КТРЭС

Лабораторная работа № 2

Размещение элементов по коммутационной

плате и распределение цепей по выводам узла

Выполнил: ст.гр. РЭ-103

Проверил:

Владимир, 2005

Цель работы: выполнить размещение элементов по плате и распределить цепи по выводам узла.

Теория.

Граф – некоторое подмножество декартовых произведений. Задаются матрицами смежности (если вершины смежные, то 1, если нет – 0) и инцидентности (матрица VxU, где V – вершины, U – ребра, если ребро выходит из вершины (т.е. инцидентно), то 1, иначе 0) или списком. Локальная степень вершины – кол-во ребер, инцидентных вершине (для графа в матрице инц. сумма в столбце всегда равна 2). Теорема Эйлера: эйлеров цикл существует, если все локальные степени его вершин четные (т.е. граф связный). Задача о коммивояжере: надо объехать все города и вернуться в исходную точку, пройдя при этом минимальное расстояние (взвешенный по ребрам граф).

Разновидности графов:

- ориентированный и неориентированный;

- орграф (дуги в виде линий со стрелками);

- неограф (множество дуг представляет собой множество неупорядоченных пар вершин, именуемых ребрами);

- мультиграф (если имеются пары вершин, соединенные более чем одним ребром);

- полный (граф, у которого любые 2 вершины смежны);

- двудольный (если множество вершин состоит из 2-х подмножеств, удовлетворяющих следующим условиям: V=V₁UV₂, V₁∩V₂=0);

- Изоморфные графы – если вершины одного из множеств представить в соответствие с вершинами другого так, что если пара вершин смежна в 1 графе, то она смежна и во 2-ом графе;

- плоский (граф расположен в плоскости так, что его ребра пересекаются только в вершинах);

- планарный (граф изоморфный плоскому).

Числа графов:

-  цикломатическое число (число ребер, которые надо удалить, чтобы получить дерево);

-  хроматическое число (число красок, которыми можно раскрасить вершины графа так, чтобы любые две смежные вершины были разного цвета);

-  число внутренней устойчивости, мощность максимального внутренне устойчивого множества (подмножество вершин графа вн. устойчиво, если любые две его вершины не смежны);

Метод Магу:

-  строится матрица инцидентности;

-  по матрице строится логическое выражение в виде КНФ;

-  используя коммутативный, дистрибутивный и ассоциативный законы, а также законы поглощения, приводят к минимальной ДНФ;

-  для каждого конъюктивного терма определяют соответствующее ему максимальное вн. устойчивое множество (ВУМ);

-  выбираем минимальное число ВУМ так, чтобы они покрывали все вершины графа (это и будет хроматическое число).

Размещение одно-габаритных элементов.

Входные: схема принципиальная электрическая, которая обычно задается списком цепей; описание монтажного пространства конструктивного узла (размеры платы, координаты посадочных мест, координаты выводов узла (контактов соединителей), координаты и размеры запрещенных зон); Описание посадочного места под конструктивный элемент.

Выходные: вектор распределения элементов по посадочным местам. Зная этот вектор и координаты посадочных мест, можно  определить координаты элементов.

ММ задачи размещения: в качестве ММ схемы обычно применяется граф, взвешенный по ребрам, ММ монтажного пространств  – регулярная прямоугольная решетка, каждая ячейка которой определяет соответствующее посадочное место.

Формализованная формулировка задачи: техническую задачу размещения