Точка - сочленение
Cтраница 2
В самом деле, точка сочленения может быть отображена на границу бесконечной грани с помощью помещения сферы на грань, содержащую эту точку на своей границе и инверсии исходного графа относительно этой сферы. При удалении точки сочленения все компоненты графа остаются плоскими, так как каждая из них будет содержать менее чем по т ребер. Таким образом, введение такой точки дает плоский граф. [16]
 |
Граф и его блоки. [17] |
Так как v - точка сочленения графа G, то граф G - о не связен и имеет по крайней мере две компоненты. Образуем разбиение V - v, отнеся к U вершины одной из этих компонент, а к W - вершины всех остальных компонент. [18]
В станках-качалках с одноплечим балансиром точка сочленения В шатуна 3 с балансиром DC находится между точкой подвеса штанг D и опорой балансира С. [19]
На рис. 3.1 v - точка сочленения, a w нет, х - мост, а у нет; отдельно приведены четыре блока графа G. Каждое ребро графа принадлежит точно одному из его блоков, так же как и каждая вершина, не являющаяся ни изолированной, ни точкой сочленения. Далее, ребра любого простого цикла графа G также принадлежат только одному блоку. Отсюда, в частности, следует, что блоки графа разбивают его ребра и простые циклы на множества, которые можно рассматривать как множества ребер. В первых трех теоремах этой главы устанавливаются несколько эквивалентных условий, обеспечивающих существование у графа точки сочленения и моста и неразделимость графа. [20]
 |
Модель - субмолекул. [21] |
Здесь через ц обозначена подвижность точки сочленения, численно равная скорости ее перемещения под действием единичной силы. [22]
Пусть блок Bh имеет bk точек сочленения. [23]
 |
Деревья, имеющие одну и две центральные или центроидные вершины.| Граф и его граф блоков и точек сочленения. [24] |
Связный граф с большим числом точек сочленения похож на дерево. [25]
Вершина v графа G называется точкой сочленения ( или разделяющей вершиной), если граф G v имеет больше связных компонент, чем G. Ребро графа G называется мостам, если его удаление увеличивает число связных компонент графа. [26]
Вершина v графа G является точкой сочленения тогда и только тогда, когда найдутся такие смежные с v вершины и и w, что v лежит на любой простой ( и-ш) - цепи. [27]
Склеивание двух блоков может уменьшить число несклеенных точек сочленения в результирующем подграфе, содержащем эти два блока, на единицу. Находим далее другой блок с одной несклеенной точкой сочленения и склеиваем его с блоком, содержащим их общую точку сочленения. Продолжаем этот процесс, пока не будет найдено оптимальное разрезание всего графа. Так как граф блоков F ( G) графа G есть дерево, следовательно, метод склеивания блоков при разрезании графов есть модификация описанного выше метода разрезания деревьев. [28]
Легко показать, что корень является точкой сочленения тогда и только тогда, когда у него больше одного сына. Эту часть оставляем в качестве упражнения. [29]
Обратно, предположим, что а - точка сочленения. Если а является корнем дерева Т, то в ней начинаются по крайней мере два ребра Т в противном случае между любой парой вершин из V - а в графе G существовал бы путь, не содержащий а. Пусть ( a, v) и ( a, w) - пара таких ребер; ясно, что v и w удовлетворяют условию теоремы. Для одной из двусвязных компонент, содержащих а, все ее вершины являются потомками а в Т; на самом деле все они ( исключая а) являются потомками вершины v, где ( a, v) - ребро в дереве Т ( почему. Очевидно, v и w являются искомыми вершинами. [30]
Страницы: 1 2 3 4