Планарность - граф
Cтраница 1
Планарность графов, имеющая многочисленные применения при прокладке алгоритмов в интегральных схемах, при исследовании изоморфизма химических и других структур, также в силу известной теоремы Понтрягина - Куратовского сводится к вычислению выполнимости или невыполнимости некоторого локального свойства. [1]
Проверка планарности графов здесь может производиться по одному из алгоритмов, описанных в предыдущем параграфе. [2]
Определение планарности графа отличается от других задач, обсуждаемых в этой главе, поскольку при изображении точек и линий на плоскости приходится больше иметь дело с. [3]
Для проверки планарности графа G цикл С стягивается в одну вершину и начинается последовательная проверка планарности связных компонент. [4]
Бадер [169] определяет планарность графа схемы, когда задан гамильтонов цикл и когда неизвестно его существование. В работе схема представляется графом, у которого вершины соответствуют контактам схемы, а ребра - проводникам. Если задан гамильтонов цикл графа, то в этом случае ребра гамильтонова цикла располагаются таким образом, чтобы он разбивал плоскость на две области - внутреннюю и внешнюю. Строится граф пересечений путем отождествления ребер графа внутри ГЦ вершинам графа пересечений. Далее проверяется, содержит ли граф пересечений циклы нечетной длины, и если содержит, то исходный граф непланарен. Если неизвестно существование ГЦ, то в этом случае граф разбивается на такое число подграфов, чтобы в каждом существовал ГЦ. Если все подграфы планарны, то проверяется планарность подграфов совместно друг с другом и делается заключение о планарности графа. [5]
 |
Базис циклов Вр. [6] |
Следовательно, условие планарности графа выполнено. [7]
Рассмотрим алгоритм определения планарности графа произвольного вида, основанный на идеях О. Затем удаляются висячие вершины с инцидентными им ребрами. UiiXi), проходящий через выбранные вершины и ребра по одному разу, в частном случае указанный цикл может быть гамильтоновым. [8]
В Maple V проверить планарность графа можно с помощью команды isplanar, которая возвращает true, если граф планарный, и false - в противном случае. [9]
Пятая глава посвящена вопросам планарности графов. [10]
Приведены основные критерии определения планарности графов. Описаны эвристические методы определения планарности и плоской укладки графов. Проанализирован генетический подход для решения данной задачи. Описан метод кодирования альтернативных решений и приведены операторы кроссинговера, мутации и инверсии, ориентированные на знания об исследуемых графах. Для непланарных графов рассмотрен ГА определения максимально планарной части графа и минимизации пересечений ребер. Временная сложность алгоритма близка к линейной зависимости. [11]
Приведенные следствия определяют зависимость планарности графа от числа его вершин и ребер и задают границы интервала по числу ребер, при попадании в который необходимо проводить дополнительные исследования, чтобы получить достоверный ответ на вопрос, планарный ли исследуемый граф. [12]
В теории графов существует понятие планарности графа. Граф называется планарным, если его можно изобразить на плоскости без самопересечений. Задача определения планарности встречается при разводке печатных плат, где ребра графа - печатные проводники, вершины - контактные площадки. [13]
Рассмотрим порядок выполнения ОМ для определения планарности графа. Например, в ходе решения задачи получена векторная хромосома, каждый ген которой представляет собой закодированную последовательность ребер. [14]
Непосредственное использование описанной процедуры для определения планарности графа с помощью ЭВМ затруднено в связи с тем, что число производных графов, которые необходимо сравнивать с / Сз, з и / Cs, получается очень большим, причем оно резко возрастает с увеличением количества вершин в исходном графе. [15]
Страницы: 1 2 3