Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Матричные эквиваленты для алгебраического задания графов

Для алгебраического задания графов и их обработки на ЭВМ ис­пользуются различные матричные эквиваленты.

Матрицей смежности А = ij]n x n (n — порядок матрицы; п x п— размер матрицы) орграфа G называется матрица, у которой: аij = т, если в G существует т дуг (xi, xj); аij = 0, если в G нет дуги (xi, xj), n — число вершин.

Матрица смежности для графа, показанного на рис.1, имеет вид

Для неографов аij равно числу кратных ребер между вершинами xi и xj, а матрица А симметрична. Матрицей инциденций B = [ bij ] n x m (n x т — размер матрицы) для орграфа называется матрица, у ко­торой: bij = 1, если xi является начальной вершиной дуги aj; bij = -1, если xi является конечной вершиной дуги аj; bij = 0, если xi не является вершиной дуги aj или aj является петлей; п — число вершин, т — число дуг в графе G.

Матрица инциденций для графа, показанного на рис.1, будет

Для неографа bij = 1, если вершина xi инцидентна ребру аj и bij = 0 в противном случае.

Для коммутационно-монтажного проектирования большое значе­ние имеют метрические свойства графов. Расстоянием d(xi, хj) между вершинами xi, хj ä Х графа G = (Х, А) называется длина кратчайшей цепи, соединяющей эти вершины. Под длиной цепи понимается число входящих в нее ребер. Функцию расстояния графа G удобно задавать матрицей расстояния D = [ dtf ]n´n,где

Для графа, показанного на рис.1, матрица D имеет вид

Для графа, рассматриваемого в системе координат XY, функция расстояний между вершинами xi и хj может быть определена следующими способами:

1. В евклидовой метрике – как расстояние между двумя точками на плоскости

.

2. В ортогональной (линейной) метрике (Манхетиново расстояние)

.

3. В нелинейной метрике

,

где k = 2, 3, ….

Поскольку матрицыА, В, D в реальных задачах конструкторского проектирования сильно разрежены, т. е. в них относительно мало не­нулевых элементов, то хранить информацию в матричной форме не­эффективно. В этом случае переходят к списковым формам представ­ления матриц. Каждая из таких матриц полностью определяет граф.

Примечание. При решении задач конструкторского проектирования часто используются другого вида матрицы, которые будут описаны при рас­смотрении конкретных алгоритмов.

 

10.4. Графотеоретические модели монтажного пространства и коммута­ционных схем.

При коммутационно-монтажном проек­тировании (см[2,3]) необходимо оптимальное размещение конструктивных эле­ментов в соответствии с коммутационной схемой их соединения в не­котором монтажном пространстве с учетом заданной конструктивной базы и в соответствии с технологией изготовления межсоединений, а также трассировка соединений.

Монтажное пространство — метрическое пространство, в кото­ром размещаются элементы какого-либо узла, и осуществляется их электрическое соединение. Различают регулярные и нерегулярные монтажные пространства.

Регулярное монтажное пространство имеет прямоугольную фор­му, и одинаковые по размерам элементы располагаются с постоянным шагом по вертикали и горизонтали (например, печатная плата ТЭЗа, показанная на рис.3).

Нерегулярное монтажное пространство характеризуется тем, что элементы имеют разные размеры и форму и не имеют точно определен­ных посадочных мест (например, подложка ИС).

Математической моделью монтажного пространства является не­ориентированный взвешенный связный граф G = (X, А), в котором множество вершин соответствует посадочным местам в координатах XY, а множество ребер — связям между вершинами на координатной сетке. Вес ребер определяется в соответствии с выбранной метрикой монтажного пространства.

Рис. 3. Печатная плата ТЭЗа Рис. 4. Коммутационная схема

 

Граф G является полным графом и отра­жает все возможные варианты расположения конструктивных эле­ментов в данном монтажном пространстве и расстояния между ними. Выбор метрики определяется технологией изготовления межсоеди­нений, например для проводного монтажа используется евклидова метрика, для печатного — ортогональная.

На рис.4 приведена коммутационная схема соединений кон­структивных элементов эi для некоторого узла, где kj соответствуют внешним выводам схемы, a bq выводам конструктивных элемен­тов.

 

<== предыдущая лекция | следующая лекция ==>
Основные сведения теории графов | Модели коммутационной схемы
Поделиться с друзьями:


Дата добавления: 2013-12-12; Просмотров: 802; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.