НОУ ІНТУЇТ | лекція | Характеристичні числа графів і їх застосування в конструкторському проектуванні РЕЗ

1. 18.3. плоскі графи При проектуванні електричних з'єднань друкованих плат до друкованого монтажу...
2. Розбиття графа на плоскі суграфом
3. 18.4. Подання конструкції РЕМ за допомогою графів

18.3. плоскі графи

При проектуванні електричних з'єднань друкованих плат до друкованого монтажу пред'являються вимоги повної відсутності або мінімального числа перетинів провідників при одношаровому (багатошаровому) друкованому монтажі. Будемо інтерпретувати малюнок електричних з'єднань графом, вершини якого відповідають контактних площадок і переходів з шару в шар, а ребра - друкованим провідникам плати. Для виконання зазначених вимог необхідно, щоб граф (часткові графи, що представляють окремі шари комутацій багатошарових друкованих плат) повністю розміщувався на площині, а його ребра перетиналися лише в вершинах при мінімізації числа вершин, відповідних контактним переходах, тобто граф (часткові графи) повинен бути плоским. У зв'язку з цим завдання визначення планарності графа і побудови його плоского зображення набуває особливого значення.

Граф називають плоским (планарним) тоді і тільки тоді, коли він має геометричну реалізацію в двомірному евклідовому просторі, тобто може бути розташований на площині так, що всі його ребра перетинаються тільки у вершинах графа.

Геометрична реалізація графа в евклідової площини, якщо вона взагалі можлива, має місце лише при певному розташуванні його вершин і ребер на площині.

Критерії планарності графів

При дослідженні принципової електричної схеми радіоелектронного пристрою, з точки зору можливості її реалізації за допомогою друкованого монтажу, конструктору важливо знати відповідь на наступні питання:

• чи є граф, відповідний даної принципової схемою, плоским;
• якщо граф плоский, то як отримати його зображення на площині без перетину ребер?

Відповімо на ці питання.

Перш за все, визначимо максимально можливе число ребер плоского графа.

Нехай, заданий граф ), Що має гамільтонів цикл. За допомогою ізоморфних перетворень перейдемо до графу , В якому ребра Гамільтона циклу не перетинаються. Тоді у внутрішній і зовнішній областях опуклою фігури, утвореної ребрами Гамільтона циклу , Можна пронести без перетинів не більше ребер. Це показано на Мал. 18.3 .

Мал.18.3.

Граф G '(X, U) з непересічними ребрами Гамільтона циклу

Отже, максимальне число некратних ребер у плоского графа

Крім того, якщо відомо, що число некратних ребер графа

то такий граф свідомо плоский.

Таким чином, можна записати наступні умови для попереднього дослідження планарності графа:

Розбиття графа на плоскі суграфом

якщо граф неплоский, то для його геометричній реалізації видаляють з окремі ребра (Переносять на іншу площину). Мінімальна кількість ребер, яке необхідно видалити з графа для його плоского зображення, називають числом планарності графа .

При винесенні цих ребер на другу площину отримують частковий граф (суграфом), що складається з ребер, який може також опинитися неплоским. Тоді знову вирішують задачу винесення окремих ребер на наступну площину і так далі.

Мінімальна кількість площин , При якому граф розбивається на плоскі суграфом , Називається товщиною графа .

Найбільший інтерес представляє розбиття на плоскі суграфом, коли переходи між площинами здійснюють тільки по вершинах графа (по ніжкам конструктивних елементів, встановлених на платі).

При використанні в сучасній апаратурі двосторонніх друкованих плат важливого значення набуває завдання пошуку критерію біпланарності довільного графа, тобто можливості розбиття його на два плоских суграфом.

Па практиці при розробці конструкції РЕМ на друкованих платах можливі два випадки:

1. Місцезнаходження конструктивних елементів на друкованій платі заздалегідь невідомо, і його потрібно визначити, мінімізувавши або число перемичок, які виконуються в місцях перетину друкованих провідників при одношаровому монтажі, або число шарів комутації при використанні багатошарових друкованих плат.

   Представивши схему електричних з'єднань конструктивних елементів у вигляді неорієнтованого графа , Переходять до пошуку раціонального розташування вершин і ребер на площині, що забезпечує мінімум перетинів ребер графа. Знайдене взаємне розташування вершин графа буде відповідати раціональному розміщенню елементів па платі, а число видаляються ребер - необхідного числа перемичок або електричних ланцюгів, які переносяться з першого шару в другій.

2. Місцезнаходження конструктивних елементів отримано на попередньому етапі розміщення. Потрібно знайти раціональне розташування ребер графа , Інтерпретує схему електричних з'єднань, при якому сумарна довжина і загальне число перетинів ребер мінімальні.

Можуть застосовуватися й інші критерії оптимізації трасування друкованих провідників.

18.4. Подання конструкції РЕМ за допомогою графів

При аналізі конструкцій РЕА застосовують в основному ненаправлення графи. Принципова електрична схема інтерпретується графом, в якому кожному конструктивному елементу ставляться в однозначна відповідність вершини, а електричним зв'язкам - ребра графа. Це дозволяє абстрагуватися від конкретних схем і перейти до їх математичним - графам, розробляти ефективні методи пошуку оптимальних конструктивних рішень.

Розглянемо схему транзисторного підсилювача ( Мал. 18.4 ).

Уявімо конструкцію у вигляді довільного неориентированного графа , у якого

a - безліч всіх електричних зв'язків елементів конструкції ( Мал. 18.5 ).

транзисторний підсилювач

Уявімо конструкцію у вигляді довільного неориентированного графа , у якого , a - безліч всіх електричних зв'язків елементів конструкції.

Довільний неорієнтовані граф для транзисторного підсилювача

виводимо клеми таким чином, щоб вивести їх як би на окрему плату - клеммник. Тоді довільний неорієнтовані граф, зображений на Мал. 18.5 , Набуде вигляду ( Мал. 18.6 ).

Зсув вершин графа

Виконаємо ізоморфні перетворення, використовуючи в якості цільової функції мінімум числа перетинів ребер графа, вкладеного в площину.

Зміщуємо вершини графа в фіксовані позиції на площині. Окремі вершини графа можуть бути попередньо закріплені, виходячи з конструктивних міркувань. У нашому випадку такими вершинами є клеми і , Взаємне розташування яких визначається контактами роз'єму.

Далі виключаємо ті з дублюючих ребер, які мають максимальну протяжність або більше число перетинів з іншими ребрами. Далі виключаємо ті з дублюючих ребер, які мають максимальну протяжність або більше число перетинів з іншими ребрами ( Мал. 18.7 ).

Модифікований граф для транзисторного підсилювача

Знайдене в результаті перетворення розташування вершин графа ( Мал. 18.7 ) Відповідає раціональному взаємного розташування елементів на платі. на Мал. 18.8 представлений загальний вигляд плати після трасування.

Розглянутий приклад ілюструє основні принципи інтерпретації принципової електричної схеми неорієнтованим графом. Далі показано виконання над графом операцій видалення окремих ребер і ізоморфних перетворень, спрямованих на оптимізацію розміщення елементів на друкованій платі. Від отриманого в результаті цих перетворень графа переходять до раціонального розміщення елементів схеми на комутаційному поле модуля.

Мал.18.8.

Двостороння друкована плата з розташованими на ній конструктивними елементами

Контрольні питання

1. Що називають цикломатическая числом графа?
2. Як використовується цикломатичне число при розгляді конструкції друкованої плати?
3. Що називають хроматичним числом графа?
4. Що являє собою біхроматична граф?
5. Який граф називають критичним?
6. Показати, як використовується хроматичної число графа при вирішенні задач конструкторського проектування РЕЗ.
7. Що являють собою плоскі графи?
8. Як використовуються плоскі графи при друкованому монтажі?
9. Показати, як здійснюється перехід від електричної схеми до графу.