АЛГЕБРАЇЧНІ МЕТОДИ ПОБУДОВИ ТОПОЛОГІЧНОГО РИСУНКА НЕПЛАНАРНОГО ГРАФА

Анотація

У цій роботі розглядаються алгебраїчні методи побудови топологічного рисунка несепарабельного непланарного графа. Доведено, що граф довільного виду можна розбити на блоки, кожен із яких являє собою максимальний нероздільний підграф. Показана структурна перебудова сепарабельного графа в несепарабельну частину графа. Застосування методів теорії обертання вершин дозволяє описувати топологічний рисунок плоскої частини графа. Так само обертання вершин індукує прості орієнтовані цикли графа. І це в підсумку дозволяє будувати топологічний рисунок графа алгебраїчними методами, не проводячи ніяких геометричних побудов на площині. Плоска частина графа будується алгоритмом виділення підмножини ізометричних циклів з потужністю, рівною цикломатичному числу графа, що характеризується мінімальним значенням функціоналу Маклейна з подальшим видаленням мінімальної кількості ребер. Подальша побудова для проведення з’єднань, віддалених у процесі планаризації, здійснюється пошуком маршрутів для пересічних з’єднань. Наведено метод вибору оптимального маршруту для проведення з’єднання на дуальному графі циклів. Розглянуто операцію включення раніше не проведених ребер у плоский топологічний рисунок.