Информационные технологии проектирования электронных средств

- 22 - Изоморфные графы могут быть получены один из другого перенумераци- ей вершин. Если граф G задан своей матрицей смежности, то его изоморфные преобразования сводятся к перестановке соответствующих строк и столбцов в матрице смежности. При покрытии функциональных схем ЭС набором стандартных корпусов микросхем необходимо установить изоморфизм между графом схемы G и ка- кой-либо частью другого графа Ğ . Это так называемые задачи изоморфного вложения. Паросочетанием графа G ( Х,Е ) называется подмножество таких ребер Е * ∈ Е , что любые два ребра e k и e s из этого подмножества не имеют общих вершин, т.е. они не смежны. При конструкторском проектировании ЭС к топологическим чертежам предъявляется требование получения плоского изображения схемы. В связи с этим возникает задача определения планарности графа. Граф G ( Х,Е ) называется плоским, если множество его ребер Е располо- жено на плоскости таким образом, что ребра имеют общие точки лишь в вер- шинах Х (рис. 9, а ). Граф, изоморфный плоскому и расположенный на плоско- сти с пересечением ребер, называется планарным (рис. 9, б ). Наименьшее число ребер, которое следует удалить из непланарного гра- фа, расположенного на плоскости, чтобы он стал планарным, называется чис- лом планарности графа. Методы определения планарности графа связаны с нахождением мини- мальных раскрасок. При конструкторском проектировании схем для много- слойного исполнения необходимо решать задачи планарного размещения графа схемы на нескольких плоскостях, причем иногда переходы между плоскостями должны осуществляться по одноименным вершинам графа. Утверждение . Граф G всегда можно расположить в r плоскостях, если существует r плоских суграфов G 1 ,G 2 ,…,G r таких, что их объединение есть ис- ходный граф  r i i G 1 = =G.