Бадер [169] определяет планарность графа схемы, когда задан гамильтонов цикл и когда неизвестно его существование. ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Мелихов А.Н. Применение графов для проектирования дискретных устройств


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

(cкачать страницу)

Смотреть книгу на libgen

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