3.2 Расслоение топологии

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