XVIII Международная студенческая научная конференция Студенческий научный форум - 2026

Введение. Современные печатные платы (ПП) становятся всё сложнее: количество компонентов растёт, а требования к компактности и энергоэффективности ужесточаются. Основная проблема проектирования заключается в трассировке – разводке электрических соединений между компонентами без пересечений.

Если соединения пересекаются в одном слое, приходится или использовать перемычки (резисторы с «нулевым» сопротивлением) и переходные отверстия между слоями (via) [1], что увеличивает стоимость и снижает надёжность платы, или использовать дополнительные слои, что усложняет производство, и, как следствие, тоже увеличивает стоимость изготовления печатной платы.

Математическую суть проблемы можно сформулировать так: «Можно ли представить электрические соединения в виде плоского графа (такого, что его можно нарисовать на плоскости без пересечений рёбер)? Если нет, то как оптимально разбить соединения на несколько слоёв?»

Анализ последних исследований и публикаций. Анализ литературы показывает, что печатные платы широко востребованы для различных электронных устройств, а задача разбиения на слои стоит достаточно остро.

Например, однослойные ПП применяются для простой аппаратуры и при макетировании электронных устройств, а двусторонние печатные платы широко применяются в электронных модулях различного назначения [2, с. 49]. Когда в работе [3, с. 2] говорится, что планарные графы широко используются в том числе в схемотехнике при создании печатных плат.

Согласно материалу НОУ ИНТУИТ [4], в котором с помощью теории графов решается задача плоской укладки схемы транзисторного усилителя, при создании печатных плат применяют неориентированные графы, каждому конструктивному элементу соответствует определённая вершина, а электрическим связям соответствуют рёбра графа.

А в статье [5] показано, что при изготовлении двусторонней печатной платы в домашних условиях используются для дальнейшего травления два фотошаблона, которые представляют собой подграфы схемы, которая является исходным графом.

Цель исследования.Исследование направлено на то, чтобы показать, как методы дискретной математики и, в частности, теории графов помогают решать задачи трассировки печатных плат.

Методы исследования. Для рассмотрения данной темы использовался теоретический анализ научной литературы и учебных материалов по теории графов и составлению печатных плат. Кроме того, были рассмотрены цены на изготовление ПП и базовые алгоритмы САПР.

Результаты исследования и их обсуждение. Проектирование печатных плат (ПП) связано с решением сложных задач компоновки и трассировки электрических соединений, т.е. определения мест расположения проводников на ПП [6].

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

Для формализации данной задачи печатная пата представляется в виде графа (неориентированного) G = (V, E), где V – это множество вершин графа, состоящее из электронных компонентов, контактных площадок; E – это множество рёбер графа, состоящее с электрических соединений.

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

Если граф планарный (а это можно проверить с помощью критерия Понтрягина–Куратовского: граф не должен содержать подграфов, гомеоморфных K₅ или K_3,3 [7]), то можно преступать к однослойной разводке, а иначе может быть эффективным заранее перед применением γ-алгоритма разбить граф на минимальное число связных подграфов, проверяя полученные графы не планарность.

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

Минимизация количества слоёв печатной платы уменьшает цену и сложность создания платы, что влечёт и повышение надёжности и конкурентоспособности изделия. Следует заметить, что, согласно данным интернет-магазина «Резонит», состоянием на 28.05.2025 добавление хотя бы второго слоя к печатной плате повышает цену на 30% [8].

Следует заметить, что для использования γ-алгоритма должно выполнятся три условия [9]: граф связный, он не является деревом и не имеет мостов. В случае нарушения первого условия необходимо совершать плоскую укладку графа отдельно по компонентам связности; в случае нарушения второго – составить его плоскую укладку тривиально.

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

Если слой уложен правильно, то САПР достаточно проверить его на выполнение формулы Эйлера [10], которая должна выполняться для плоских графов: V – E + F = 2, где V – это количество вершин, E – рёбер, а F – граней.

Выводы. Итак, учитывая всё вышесказанное, можно утверждать, что методы теории графов, в частности представление платы как графа и её плоская укладка, применимы на практике для проектирования (в том числе автономного) печатных плат.

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

Список литературы

1. Via (electronics): // Wikipedia. [Электронный ресурс]. URL: https://en.wikipedia.org/wiki/Via_(electronics). (Дата обращения: 27.05.2025).

2. Конспект лекций. Типы печатных плат и их конструктивные особенности, стр. 49–58: // Электронная образовательная система МГТУ им. Н.Э.Баумана. [Электронный ресурс]. URL: https://e-learning.bmstu.ru/iu4/pluginfile.php/689/mod_resource/content/2/tom_09_1.4.%20типы%20печатных%20плат%20и%20их%20конструктивные%20особенности.pdf. (Дата обращения: 27.05.2025).

3. Гадратова П.М. Укладка графа на плоскости: // Саратовский национальный исследовательский государственный университет имени Н.Г. Чернышевского. [Электронный ресурс]. URL: http://elibrary.sgu.ru/VKR/2017/10-05-01_018.pdf. (Дата обращения: 27.05.2025).

4. Характеристические числа графов и их применение в конструкторском проектировании РЭС: // НОУ ИНТУИТ. [Электронный ресурс]. URL: https://intuit.ru/studies/courses/650/506/lecture/11521?page=2. (Дата обращения: 27.05.2025).

5. Современный способ изготовления двусторонних печатных плат с высоким разрешением своими силами. Часть 1: // Современная электроника и технологии автоматизации. [Электронный ресурс]. URL: https://www.cta.ru/articles/soel/2023/2023-8/169785/. (Дата обращения: 27.05.2025).

6. Трассировка печатных плат: // Википедия. [Электронный ресурс]. URL: https://ru.wikipedia.org/wiki/Трассировка_печатных_плат. (Дата обращения: 27.05.2025).

7. Теорема Понтрягина-Куратовского: // Университет ИТМО. [Электронный ресурс]. URL: https://neerc.ifmo.ru/wiki/index.php?title=Теорема_Понтрягина-Куратовского. (Дата обращения: 27.05.2025).

8. Прайс-лист на печатные платы: // Резонит. [Электронный ресурс]. URL: https://www.rezonit.ru/price_pcb/. (Дата обращения: 27.05.2025).

9. Гамма-алгоритм: // Университет ИТМО. [Электронный ресурс]. URL: https://neerc.ifmo.ru/wiki/index.php?title=Гамма-алгоритм. (Дата обращения: 27.05.2025).

10. Формула Эйлера: // Университет ИТМО. [Электронный ресурс]. URL: https://neerc.ifmo.ru/wiki/index.php?title=Формула_Эйлера. (Дата обращения: 27.05.2025).