Cтраница 1
Определение планарности графа отличается от других задач, обсуждаемых в этой главе, поскольку при изображении точек и линий на плоскости приходится больше иметь дело с. [1]
Рассмотрим алгоритм определения планарности графа произвольного вида, основанный на идеях О. Затем удаляются висячие вершины с инцидентными им ребрами. UiiXi), проходящий через выбранные вершины и ребра по одному разу, в частном случае указанный цикл может быть гамильтоновым. [2]
Приведены основные критерии определения планарности графов. Описаны эвристические методы определения планарности и плоской укладки графов. Проанализирован генетический подход для решения данной задачи. Описан метод кодирования альтернативных решений и приведены операторы кроссинговера, мутации и инверсии, ориентированные на знания об исследуемых графах. Для непланарных графов рассмотрен ГА определения максимально планарной части графа и минимизации пересечений ребер. Временная сложность алгоритма близка к линейной зависимости. [3]
Непосредственное использование описанной процедуры для определения планарности графа с помощью ЭВМ затруднено в связи с тем, что число производных графов, которые необходимо сравнивать с / Сз, з и / Cs, получается очень большим, причем оно резко возрастает с увеличением количества вершин в исходном графе. [4]
Рассмотрим порядок выполнения ОМ для определения планарности графа. Например, в ходе решения задачи получена векторная хромосома, каждый ген которой представляет собой закодированную последовательность ребер. [5]
В этой главе далее рассмотрены два циклических алгоритма определения планарности графа схемы, приведен способ определения числа планарности и оценки числа планарных и непланарных графов. [6]
Дана и Чена [175] и др. приведены алгоритмы, которые используют матрицу линейно независимых циклов для определения планарности графа. [7]
При конструировании схем к их топологическому чертежу предъявляется требование получения, либо плоского изображения схем, либо плоского изображения частей схем. В этой связи возникает задача определения планарности графа. [8]
При проектировании модульных схем, как правило, к топологическому рисунку предъявляются требования получения плоского изображения схемы либо плоского изображения частей схемы. В этой связи возникает задача определения планарности графа схемы. [9]
Вводится понятие числа планарности. Приводятся приближенные оценки числа планарных и непла-нарных графов. Рассматривается методика определения планарности графа схемы цифрового автомата. Если граф планарен, то получается его плоская реализация, в противном случае выполняется декомпозиция графа на плоские подграфы. Излагается метод разбиения графа на плоские суграфы с использованием внутренне устойчивых множеств. Приведены ЛЯПАС-программы основных алгоритмов. [10]