12. Раскраска графов.

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

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

Задача NP трудна и не решает проблемы, потому что число слоев обычно ограничено, а хроматическое число (минимальное число цветов) может оказаться больше заданного числа слоев, кроме того, не учитывается возможность перехода со слоя на слой в произвольном месте - это совсем другая задача.

Алгоритм раскраски графа по степеням вершин

Дано: G=(V,X) - связный граф. Требуется найти вершинную раскраску графа и приближенное значение хроматического числа K. Необходимо:

1. Вычислить степени вершин. Положить K=1. (степень – сколько смежных ребер)

2. Просмотреть вершины в порядке невозрастания степеней и окрасить первую неокрашенную вершину в цвет № K.

3. Просмотреть вершины в порядке невозрастания степеней и окрасить в цвет № К все вершины, которые не смежны вершинам, уже окрашенным в цвет №К.

4. Если все вершины окрашены, то К-искомое хроматическое число, Иначе К=К+1 и переход к пункту 2.

12. Сеточные, бессеточные и топологические методы трассировки.

Прямоугольная сетка:

требующаяся память и быстродействие напрямую не зависят от величины проекта (схемы): для одного и того же проекта уменьшение шага сетки ведёт к квадратичному увеличению числа её узлов (требуется большая память) и к квадратичному увеличению времени решения (уменьшается быстродействие);

неэкономично используются ресурсы коммутационного пространства: если какая-либо деталь топологического элемента занимает лишь часть площади дискрета, то всё равно оккупируется весь дискрет; каждая трасса занимает весь дискрет целиком.

существуют дополнительные сложности, связанные с непопаданием элементов топологии в сетку;

происходит неоправданное увеличение длины трасс (проводятся два катета или ломаная вместо гипотенузы);

высока трудоемкость модификации топологического рисунка, и, как следствие, низка эффективность процедур оптимизации (из-за локальности изменения геометрии трасс процедуры быстро заходят в тупик).

Модификации сетки: свободное для трасс монтажное пространство в виде множества отрезков (на одном слое горизонтальные, на другом - вертикальные), при фиксации трассы как совокупности фрагментов отрезков последние делятся на части.

Shape-based: учет реальной геометрии элементов топологии, а не аппроксимирующих прямоугольников, представление трасс в виде последовательности отрезков прямых, а не дискретов.

Бессеточность.Shape-based трассировщики, например, SPECCTRA работают с геометрическими объектами (контактными площадками, переходными отверстиями и линейными фрагментами проводников), не раскладывая их в набор дискретов.

Триангуляция: число ячеек пропорционально числу элементов топологии, следовательно, размеры модели линейно зависят от размера проекта (числа контактов и т. п.), следовательно, достигается минимум памяти и максимум быстродействия. Но, к сожалению, в этой модели сложно (невозможно) учесть реальную геометрию элементов.

Топологический метод.

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

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

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

• Современные технологии обычно позволяют проводить дорожки между контактами элементов РЭА или под планарными контактами в другом слое. Отсутствие учёта такой возможности топологическим трассировщиком будет приводить к неоптимальным решениям из-за того, что чисто топологическая модель коммутационного пространства неадекватно отражает свойства реального конструктива.