Любое дерево

Cтраница 4

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

Теорема, очевидно, справедлива, если дерево состоит из одной ветви и имеет две вершины. Это соотношение не нарушится, пока конфигурация с добавленными ветвями остается деревом. Например, любое дерево Т графа G ( рис. 1 - 8) содержит ат4 - 13 ветви. Из теоремы ( 1 - 2) вытекает ряд важных следствий. [47]

Неприводимые системы образующих, целиком состоящие из транспозиций, называют базисами симметрической группы Sn - Поскольку графы Пойа систем I и II, приведенных на с. По виду графов Пойа базис I называется линейным базисом, а базис II -звездообразным. Покажем, что любое дерево с п вершинами содержит п - 1 ребро. [48]

Конкретными реализациями такого процесса являются корневые деревья, поэтому необходимо перейти от бескорневого молекулярного леса к корневому ( клану), не нарушив при этом статистики первого. Такой переход делается следующим образом. Каждому узлу в любом дереве молекулярного леса ставится в соответствие одно корневое дерево из клана, корнем которого является этот узел. Остальные узлы и висячие вершины некорневого дерева переходят в соответствующие узлы и вершины этого же корневого дерева произвольным образом, но так, чтобы сохранилась раскраска и смежность. Таким образом, любому молекулярному дереву с / узлами соответствуют в клане / корневых деревьев с той же конфигурационной структурой и раскраской. Один из способов их выбора для молекулярного дерева с / 3 изображен на рис. 2.4. Из такого определения клана следует, что весовое распределение fw ( l) молекул должно отвечать распределению корневых деревьев в соответствующем клане. Другими словами, вероятность принадлежности произвольно выбранного мономерного звена определенного типа молекуле с числом звеньев / совпадает с вероятностью того, что это звено является корнем некоторого корневого дерева с таким / и равна, следовательно, доле деревьев с этим числом звеньев в клане. То же самое верно и для весовой доли любого ( / /) - изомера, поскольку все корневые деревья, отвечающие каждому такому изомеру в клане, имеют одинаковую с ним конфигурационную структуру и раскраску. [49]

Универсальная связанная структура представления дерева. [50]

По дереву на рис. 2.6 легко перемещаться в обоих направлениях. Переход вверх на один уровень из вершины а [ т ] можно выполнить, разделив m пополам и отбросив дробную часть. Рассмотренная структура применима к любому дереву с постоянным количеством ребер, выходящих из вершин. [51]

С другой стороны, нетрудно видеть, что x ( G) 1 тогда и только тогда, когда G - вполне несвязный граф, и что X ( G) 2 тогда и только тогда, когда G - двудольный граф, отличный от вполне несвязного графа. G не является вполне несвязным графом, то X ( G) 2 тогда и только тогда, когда G не содержит циклов нечетной длины. В частности, заметим, что любое дерево, имеющее не менее двух вершин, является 2-хроматическим, и то же верно для любого циклического графа с четным числом вершин. [52]

Условные обозначения основных элементов электрической си. [53]

На заре развития электротехники не было условных обозначений, и учение и инженеры вынуждены были изображать каждый раз общие виды и разрезы электрооборудования. Но далее, подобно тому, как с развитием культуры и повышением общего уровня цивилизации разговорный язык становился вес более абстрактным, язык электротехники также совершенствовал способы изображения наиболее общих свойств широкого класса устройств. Как при слове дерево можно представить себе любое дерево - дуб, сосну, ель, молодое дерево и старое, так же при начертании условного изображения трансформатора можно подразумевать и мощный силовой трансформатор, способный преобразовать огромные потоки энергии, и трансформатор миниатюрный, используемый для питания электронных приборов. [54]

Листья дерева ( вершины степени 1), присоединенные к одной и той же вершине, могут быть переставлены между собой, и это будет сохранять матрицу смежности неизменной. В этом процессе обрезки дерева все листья, присоединенные к корню ( или к разветвлению), обрезаются совместно. Таким образом, обрезка деревьев позволяет определять группу симметрии любого дерева. Вершины 1, 7 и 8 могут быть переставлены между собой всеми возможными способами. [55]

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