6.20. Печатные схемы

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

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

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

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

Если допускаются дополнительные отверстия и любые перемычки через плату, то этом случае можно отпечатать любую сеть. Можно, например, начать с вычерчивания сети на плоскости таким образом, чтобы самое большее два провода пересекались в любой точке, которая не является заранее заданным узлом. После этого сеть почти полностью можно отпечатать на одной стороне платы, а в каждом месте пересечения, где не должно быть соединения проводов, один из проводов с помощью двух отверстий и перемычек должен быть пропущен на другую сторону и частично отпечатан на этой стороне. Таким образом, на одной из сторон платы отпечатываются только небольшие участки проводов. Граничные оценки на число такого типа пересечений проводов даны в разделе 6.7.

Предположим теперь, что требуется отпечатать данную сеть при минимально возможном числе дополнительных отверстий в плате (не считая отверстий в вершинах). Любой способ печати схемы можно изобразить» вычертив сеть на плоскости, используя для этого два типа дуг. Жирными линиями можно показывать, например, дуги, располагаемые на одной стороне платы, а тонкими линиями — дуги, располагаемые на другой стороне.

Задача может быть теперь переформулирована таким образом: найти наименьшее число дополнительных вершин степени 2 (соответствующих точкам, в которых

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