Вершина - степень
Cтраница 1
Вершина степени 1 называется висячей, а степени 0 - изолированной. [1]
Вершина степени один называется висячей. Из оп-пределения дерева и теоремы 1 вытекает, что всякое дерево имеет йо крайней мере две висячие вершины. [2]
Листья дерева ( вершины степени 1), присоединенные к одной и той же вершине, могут быть переставлены между собой, и это будет сохранять матрицу смежности неизменной. В этом процессе обрезки дерева все листья, присоединенные к корню ( или к разветвлению), обрезаются совместно. Таким образом, обрезка деревьев позволяет определять группу симметрии любого дерева. Вершины 1, 7 и 8 могут быть переставлены между собой всеми возможными способами. [3]
Предположим, что v - вершина степени г в графе G. Если G является регулярным графом степени г, то, естественно, после любого числа r - кликовых вставок получающийся больший граф также будет г-регулярным. [4]
Если цикл S содержит одну вершину степени 2, скажем Уь а степени вершин Vt больше 2 для всех /, 2 / г, будем рассуждать следующим образом. [5]
Если в графе G имеется kt вершин степени /, то выражение ( l V. [6]
Если трехсвязный планарный граф & не имеет вершин степени больше трех, а если имеет, то они не образуют со связывающими их ребрами ни одного внутреннего цикла, тогда граф Q - элементарный. [7]
 |
Некоторые г-критические графы. [8] |
Пусть G является т-критическим графом, и а - вершина степени 2 в графе G. Если вершины у и z смежны между собой, то множество x y z индуцирует связную компоненту графа G. Если же вершины у и z не смежны, то никакая вершина, кроме х, не является смежной с ними обеими, и, кроме того, если мы сожмем ребра ху и xz, то результирующий граф G будет г-критическим. [9]
Если при этом фиксированный трехвалентный элемент графа G содержит вершину степени 3, инцидентную треугольнику, то редукция уменьшает число ребер графа G по крайней мере на одно ребро. Если же граф G не содержит такой вершины, то покажем, что в этом случае существует конечная последовательность редукций, приводящих к графу, содержащему вершину степени 3, инцидентную треугольнику. Очевидно, что каждый граф G, полученный редукцией планарного трехсвязного графа G, также планарен и трех-связен. [10]
Пусть корневое дерево имеет k висячих вершин и не имеет вершин степени 2, отличных от корня. [11]
 |
Перспективное изображение МГ, соответствующих трем конфор-мациям молекулы циклогексана. [12] |
Рассмотрим теперь МГ с циклическими подграфами, в которых имеются только вершины степени три и единица. Простейшим представителем такого класса соединений является молекула бензола. [13]
Допустим, что G - произвольная карта; если она содержит какие-либо вершины степени 2, то их можно удалить1), что не изменит раскраску. Таким образом, остается показать, как избавиться от вершин, степень которых больше или равна четырем. [14]
Схему можно также представлять в виде ориентированного ациклического графа, у которого вершины входной степени 0 ( входы) помечены исходными переменными; остальные вершины ( функциональные элементы) помечены функциями из базиса ( при этом входная степень вершины должна совпадать с количеством аргументов ее пометки); ребра помечены числами, указывающими номера аргументов; вершины выходной степени 0 ( выходы) помечены переменными, описывающими результат работы схемы. УЙ, из которых ведут ребра в данную вершину v, вершина v получает значение у fv ( yi, , ykv), где fv - базисная функция, которой помечена вершина. При переходе к графу схемы мы опускаем несущественные присваивания, которые ни разу не используются на пути к выходным вершинам, так что они никак не влияют на результат вычисления. [15]
Страницы: 1 2 3 4