Бадер [169] определяет планарность графа схемы, когда задан гамильтонов цикл и когда неизвестно его существование. ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Мелихов А.Н.
Применение графов для проектирования дискретных устройств
Бадер [169] определяет планарность графа схемы, когда задан гамильтонов цикл и когда неизвестно его существование. В работе схема представляется графом, у которого вершины соответствуют контактам схемы, а ребра - проводникам. Если задан гамильтонов цикл графа, то в этом случае ребра гамильтонова цикла располагаются таким образом, чтобы он разбивал плоскость на две области - внутреннюю и внешнюю. Строится граф пересечений путем отождествления ребер графа внутри ГЦ вершинам графа пересечений. Далее проверяется, содержит ли граф пересечений циклы нечетной длины, и если содержит, то исходный граф непланарен. Если неизвестно существование ГЦ, то в этом случае граф разбивается на такое число подграфов, чтобы в каждом существовал ГЦ. Если все подграфы планарны, то проверяется планарность подграфов совместно друг с другом и делается заключение о планарности графа.