Никакое ребро

Cтраница 3

Граф называется внешнепланарным, если его можно изобразить на плоскости так, чтобы никакие ребра не пересекались и все вершины графа лежали на границе бесконечной грани этого графа. [31]

Лемма 3.5. В общем случае геодезический путь есть путь, который проходит через чередующуюся последовательность вершин и ( возможно, пустых) реберных последовательностей, таких что образ пути при развертке вдоль любой реберной последовательности представляет собой прямолинейный отрезок, а угол, образованный путем при прохождении через вершины, больше или равен я. Общий вид оптимального пути такой же, как и геодезического, за исключением того, что никакое ребро не может появиться более чем в одной реберной последовательности и каждая реберная последовательность должна быть простой. [32]

Значит, наш исходный цветущий лес состоит из множества V ( G) и не содержит никаких ребер. [33]

Тогда можно определить отношение эквивалентности с этими классами Bk, полагая aRb тогда и только тогда, когда а п b принадлежат одному множеству Bk. В соответствующем графе G ( R) любые две вершины из одного множества Bk будут соединены ребром, и никакое ребро не соединяет вершины из различных множеств. [34]

Осговное дерево, построенное поиском в глубину. 208. [35]

Поиск в глубину особенно полезен для нахождения двусвязных компонент неориентированного графа. Иными словами, если узел v - не предок и не потомок узла ш в остовном лесу, то v и w не могут соединяться никаким ребром. [36]

При поиске в глубину на ориентированном графе в дополнение к древесным ребрам возникает еще три типа ребер. Это обратные ребра, такие, как ( vs, v) на рис. 5.13 6, поперечные справа налево, такие, как ( и4, УЗ) на том же рисунке, и прямые ребра, такие, как ( Vi, о4) - Однако никакое ребро не идет из узла с меньшим номером, присвоенным в процессе поиска в глубину, в ребро с большим номером, если только последнее не является потомком первого. [37]

Рассмотрим все ребра куба Вп некоторого направления. Никакое ребро не может содержать двух выделенных собственных точек. Отсюда и вытекает утверждение. [38]

Вынесение линий на картинную плоскость является характерным приемом метода архитекторов. На рис. 68, а он применен для изолированной точки А, расположенной в плоскости основания. Так как здесь никаких ребер и граней нет, то из точки А проводится произвольная прямая АВ до пересечения со следом картинной плоскости k в точке В. [39]

Последовательность ребер графа, таких, что конец одного ребра является началом следующего, называется цепью. Вершины 2, 6 являются соответственно началом и концом цепи. Цепь называется простой, если в ней никакое ребро не встречается дважды, и элементарной, если в ней никакая вершина не встречается дважды. [40]

Первичная структура молекул РНК фиксирована. В то же время ее вторичная структура потенциально весьма изменчива, но подчиняется двум ограничениям. Первое из них состоит в том, что никакое ребро типа Ь не может быть инцидентным более чем одной вершине, а, согласно второму, структура с ребрами типа Ь является плоской. [41]

Никакое ребро в B ( L) не может быть излишним, так как иначе оно приводило бы к уменьшению В. В В существует только одно ребро, соединяющее пару листовых множеств LI и L2 в G ( и в В), так как если одно такое ребро содержится в В, то другие, очевидно, являются излишними. Ребра из В образуют порождающий граф для G, и никакие ребра из В не могут быть излишними, так как это снова приводило бы к уменьшению В. [42]

В графе ( V, А) имеется ровно, один узел S. V, называемый стартовым узлом, не являющийся конечным узлом никакого ребра; имеется ровно один узел Я. У, называемый стоп-узлом, который не является начальным узлом никакого ребра, и каждый узел и находится на некотором пути от S к Я. [43]

Если подграф Н является ( /, 7) - оптимальным и Н получается из Н локальным пополнением, то верно также, что Н может быть получен из подграфа Н локальным пополнением. Если подграф Н является ( /, ( - оптимальным, то никакое локальное пополнение не может изменить никакого ребра, инцидентного множеству С. Поэтому мы приходим к следующему результату. [44]

Если маршрут имеет начальную вершину, но не имеет конечной вершины, или если он имеет конечную вершину, но не имеет начальной, то он называется односторонне-бесконечным. Если маршрут не имеет ни начальной, ни конечной вершины, то он называется дву-сторонне-бесконечным. Маршрут назовем нетривиальным, если он содержит хотя бы одно ребро; для систематичности рассуждений вводится еще нуль-маршрут, не содержащий никаких ребер. [45]

Страницы: 1 2 3 4