Cтраница 2
В первой главе были рассмотрены основные критерии планарности графа. Однако использование этих критериев для распознавания планарности графов схем с помощью ЦВМ затруднительно, так как их применение требует содержательного рассмотрения графа и связано со значительным перебором. Поэтому необходимо строить алгоритмические методы определения планарности, основанные на известных критериях и позволяющие формализовать процедуру распознавания графов с достаточно большим числом вершин и ребер. [16]
Удаление одного ребра из гамильтонова цикла приводит к планарности графов данного вида. [17]
В этой главе далее рассмотрены два циклических алгоритма определения планарности графа схемы, приведен способ определения числа планарности и оценки числа планарных и непланарных графов. [18]
В теоремах 12В и 12С мы дали необходимые и достаточные условия планарности графа, а именно: он не должен содержать подграфов, гемеоморфных или стягиваемых к / Q или к Кз з - Теперь нашей целью является обсуждение условий совсем другого вида, а именно условий, включающих понятие двойственности. [19]
Достаточность в теореме 2.1 для случая п 1 является следствием критерия Понтрягина-Куратовского планарности графов. [20]
Татта [209] предлагается построение по матрице инциденций матрицы разрезов и дальнейшее определение планарности графов. [21]
Дана и Чена [175] и др. приведены алгоритмы, которые используют матрицу линейно независимых циклов для определения планарности графа. [22]
Как мы вскоре увидим, графы / С5 и / Сз з играют исключительную роль при характеризации планарности графов. Приведенные выше следствия очень полезны в исследовании пленарных графов, в особенности максимальных планарных графов. [23]
Методы, относящиеся к первому классу, основаны на проверке некоторых критериев и дают необходимые и достаточные условия планарности графов. [24]
Так как наибольшим числом ребер в плоском графе обладает граф, у которого каждая грань есть треугольник, то получаем необходимое условие планарности графа в терминах числа ребер. [25]
При конструировании схем к их топологическому чертежу предъявляется требование получения, либо плоского изображения схем, либо плоского изображения частей схем. В этой связи возникает задача определения планарности графа. [26]
При проектировании модульных схем, как правило, к топологическому рисунку предъявляются требования получения плоского изображения схемы либо плоского изображения частей схемы. В этой связи возникает задача определения планарности графа схемы. [27]
В первой главе были рассмотрены основные критерии планарности графа. Однако использование этих критериев для распознавания планарности графов схем с помощью ЦВМ затруднительно, так как их применение требует содержательного рассмотрения графа и связано со значительным перебором. Поэтому необходимо строить алгоритмические методы определения планарности, основанные на известных критериях и позволяющие формализовать процедуру распознавания графов с достаточно большим числом вершин и ребер. [28]
Оказывается, возникающие проблемы могут быть достаточно просто решены, если от принципиальных схем механизмов перейти к их изображениям в виде специальных графов размещения. При этом процесс исследования геометрической совместности схем заменяется анализом планарности графов [24, 23], отображающих только те свойства схем, которые являются существенными для размещения механизма в пространстве. Если при анализе графов окажется, что они планарны, то делается вывод о геометрической совместности соответствующей схемы. В противном случае, механизм не может быть размещен в пространстве без пересечения звеньев. [29]
Заметим, что при построении матрицы РЬ кратность ребер можно не учитывать, так как она не влияет на планарность графа. [30]