МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ

РАДИОТЕХНИКИ. ЭЛЕКТРОНИКИ И АВТОМАТИКИ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Кафедра ВТ

КОНТРОЛЬНАЯ РАБОТА

По дисциплине: Автоматизация производства

Тема: Разработка плоского графа – модели ПП

СТУДЕНТ: Купцов Г.Г.

ГРУППА: ВТ-2-99

ШИФР: С-991080

РУКОВОДИТЕЛЬ

ПРОЕКТА: Одиноков В.Г.

Москва 2004

Содержание

Задание…………………………………………………………….……………………………..3

Теоретическая часть……………………………………………………………………………..4

Анализ задания……. ……………………………………………………………………………6

Решение……………. ……………………………………………………………………………8

Определение числа сторон (слоев) печатного монтажа……………………………………..11

Выводы……………. …………………………………………………………………………...13

Задание

Разработать плоский граф – модель печатной платы. Определить минимальное количество слоев (сторон) печатной платы. Каждая вершина матрицы есть ЭРЭ типа микросхема

Теоретическая часть

Понятие графа:

Граф есть множество вершин Х, и множество ребер U. Где Х={x1, x2, х3, х4}, которые на модели печатной платы представляют собой контактные площадки. U=[{x1 x2} {x2 x3} {x3 x4} {x4 x1} {x2 x4} {x1 x3}, которые на модели печатной платы являются связями (проводниками) между контактными площадками.

Моделью печатной платы является плоский граф.

Граф G(XU) – плоский если его можно сделать планарным.

Граф G(XU) – планарный если его ребра пересекаются лишь в вершинах.

Ребро Uij инцидентно вершинам Xi, Xj если оно связывает эти вершины. Например ребро {х1 х2} инцидентно вершинам х1 и х2, и не инцидентно х3.

Количество ребер инцидентных какой-либо вершине xi называется локальной степенью этой вершины. Например локальная степень х1=3.

Граф называется связным если 2 его вершины связаны.

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

Говорят, что если количество ребер r>3*(n-2), то граф заведомо неплоский, где r – количество ребер, n – количество вершин.

Говорят, что если r<=(n+2), то граф заведомо плоский.

Говорят, что если (n+2)<r<=3*(n-2), то это неопределенный граф.

В этом случае пользуются теоремой Понтрягина - Коротовского.

Теорема Понтрягина – Коротовского гласит:

• Необходимое и достаточное условие, при котором граф G является плоским состоит в том, что граф G не должен содержать частичных подграфов типа:

Тип 1
Тип 2

Анализ задания

Согласно заданию, ниже приведен граф.

Граф содержит 12 вершин и 32 ребра. Для упрощения вида, убираем все кратные ребра.

Количество ребер r = 22, количество вершин n = 12.

1. Если r > 3(n-2) – граф неплоский

2. Если r  (n+2) – граф плоский

3. Если (n+2) < r< 3(n-2) – неопределенно

Подставим значения:

1. 22 > 3(12-2) => 22 >30 – не выполняется

2. 22  (12+2) => 22  14 – не выполняется

3. 12 + 2  22  3(12-2) => 14  22  30 – выполняется.

Вывод: имеет место неопределенность.

По условию задания – каждая вершина нашего графа есть ЭРЭ типа микросхема. Поэтому наш граф можно представить в виде:

После того как будет определено количество слоев, данная схема должна быть преобразована так, чтобы проводники (связи) равномерно распределились по всем слоям.

Решение

Выбираем первоначальную грань. Согласно определению, грань – это область плоскости, ограниченная ребрами связного плоского графа и не содержащая внутри себя ни ребер, ни вершин. Возьмем грань (9,12,11,2,4).

Далее к выбранной грани достраиваем кусок 9,12,7.

Достраиваем следующий кусок 9,12,10.

Достраиваем следующие куски 12,10,1.

Достраиваем следующий кусок 1,12,3.

Достраиваем следующий кусок 3,12,11,5.

Достраиваем следующий кусок 3,5,8.

Достраиваем следующие куски 1,3,8 и 11,5,8.

Достраиваем ребро 6,10:

После всех преобразований остались вершины 1, 7, и 5, которые по исходной схеме должны быть соеденены ребрами {1, 7}, {1, 5}. Но провести эти отрезки так, чтобы не было пересечений с окончательным плоским графом нельзя. Из этого делаем вывод, что для реализации данной модели печатной платы мне необходимо 2 стороны (слоя), т.е. данная модель будет реализована на двусторонней печатной плате.

Не вошедшие в окончательный граф ребра показываем пунктиром:

Определение числа сторон (слоев) печатного монтажа.

Как уже было сказано, данная модель печатной платы может быть реализована на двусторонней печатной плате (или двухслойной). При решении, мы получили плоский граф, ребра которого пересекаются лишь в вершинах. Ребра {1 7} и {1 5}, образующие пересечения могут быть реализованы на другой стороне печатной платы.

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

Учитывая, что по условию каждая вершина есть ЭРЭ типа микросхема, данный граф представляем в виде модели печатной платы, где условно все вершины – микросхемы. Проводники (ребра графа) печатной платы распределяем так, что все пересечения идут по 2й стороне печатной платы.

Сторона А
Сторона B

ВЫВОДЫ

В результате моделирования получили плоский граф – модель печатной платы. На этапе представления плоского графа в виде модели печатной платы, где каждая вершина – микросхема, столкнулись с тем, что невозможно провести проводники (ребра графа) по двум сторонам печатной платы без пересечений. Решением данной проблемы стало произвольное (не по порядку) размещение микросхем на печатной плате.

В данной работе мы научились разрабатывать модели печатной платы, определять минимальное количество слоев (сторон) печатной платы.

5