3.4 Реализация алгоритмов решения задачи трассировки

Составим матрицу длин для блока №1

Выбираем модуль А4, просматриваем первую строку, находим первый минимальный элемент - длина соединения между модулями А4 и А1 равна 8 единиц, проводим это соединение, вычеркивая первый и третий столбцы. Далее алгоритм повторяется до полного покрытия пространства трассами. Минимальное покрывающее дерево, построенное с помощью алгоритма Прима для блока №5, представлено на рисунке 6. Исходный граф схемы представлен на рисунке 7, а граф пересечения для определения хроматического числа - на рисунке 8.

Рисунок 6 ? Минимальное покрывающее дерево для блока №1

Рисунок 7 ? Исходный граф схемы

Рисунок 8 ? Граф пересечения

На рисунке 7 видно два пересечения ребер исходного графа, с помощью этого рисунка построен граф пересечений, содержащий два ребра и десять вершин, окрашенных в два цвета. Вершина u6 окрашена в черный цвет, остальные вершины - в серый. Это значит, что печатная плата содержит только два слоя, в одном из которых находятся проводник u6, в другом слое - остальные проводники.

Для реализации волнового алгоритма проведения проводников выбраны соединения между элементами А1 и А7 (1/4 и 7/4), результаты представлены на рисунке 9, и между элементами А8 и А9 (7/2 и 10/8) - результат на рисунке 10.

Рисунок 9 ? Распространение волны для соединения модулей А4 и А10.

Рисунок 10 ? Распространение волны для соединения модулей А7 и А10.