Точка - сочленение
Cтраница 4
 |
Остовное дерево с со значениями функции НИЖНИЙ. [46] |
Что касается корректности алгоритма, то лемма 5.5 гарантирует, что точки сочленения будут найдены правильно. Даже если корень не является точкой сочленения, алгоритм обращается с ним как с таковой, чтобы выделить двусвязную компоненту, содержащую корень. [47]
На рис. 8.6 показан граф блоков G, у которого каждая точка сочленения принадлежит точно двум блокам. Дерево Т, для которого G - реберный граф, строится следующим образом. Сначала образуется граф блоков В ( G), а затем добавляются новые вершины в качестве вершин, не являющихся точками сочленения графа G, и ребра, соединяющие каждый блок с новыми вершинами. [48]
Упражнение 5.4. Показать, что если граф связен и не имеет точки сочленения, то его матрица разрезов содержит матрицу инциденций. [49]
Часто можно заметить, что связный граф с достаточно большим числом точек сочленения похож на дерево. Дерево блоков и точек сочленения графа G ( обозначение: be ( G)) представляет собой граф, у которого множество вершин есть объединение множества блоков и множества точек сочленения графа G и две вершины смежны, если одна из них соответствует блоку графа G, а другая - точке сочленения графа G, принадлежащей этому блоку. Легко показать, что если G - связный граф, то граф be ( G) действительно является деревом. [50]
Пусть связный граф О имеет 1-разделение ( Н К) с точкой сочленения V, и пусть Н и К - планарные графы. Тогда граф С планарен. [51]
Для каждого тела, образованного при разбиении, составляем уравнения моментов относительно точки сочленения. Полученные уравнения дополняем двумя уравнениями равновесия для всей конструкции в целом. [52]
 |
Разбиение графа на дерево и хорды. [53] |
Некоторые из величин 2 / могут быть равны О Соответствующие вершины характеризуют точки сочленения трубопроводов и в них нет внешнего притока. [54]
Непосредственно из определения графа L ( G) вытекает, что каждая точка сочленения графа L ( G) есть мост графа G, не являющийся концевым ребром, и обратно. [55]
Пусть у связного графа С число блоков равно N, а число точек сочленения равно г. Пусть п, - число ответвлений в - й точке сочленения. [56]
Этого можно избежать, изменив, например, гидравлические сопротивления в окрестности точки сочленения. [57]
Тогда существует 1-разделение ( Я, / () графа ОА с Точкой сочленения к, и можно считать, что вершина 1л принадлежит подграфу Я. С графа О имеет только одну соединяющую вершину. Однако в силу теоремы 111.2 и двусвяз-ности графа О это невозможно. [58]
Страницы: 1 2 3 4