Блок - граф
Cтраница 2
Теоремы 111.27 и 111.28 показывают, что между множеством ответвлений в вершине х в графе О и множеством блоков графа О, содержащих х, существует взаимно однозначное соответствие. Каждое такое ответвление содержит ровно один такой блок и, наоборот, каждый такой блок содержится только в одном таком ответвлении. Из теоремы 111.21 следует, что в вершине х существуют два или более ответвлений тогда и только тогда, когда она является точкой сочленения графа О. [16]
Теорема 111.17. Если А - петля или перешеек в графе О, то подграф О - А является блоком графа О. [17]
На рис. 3.1 v - точка сочленения, a w нет, х - мост, а у нет; отдельно приведены четыре блока графа G. Каждое ребро графа принадлежит точно одному из его блоков, так же как и каждая вершина, не являющаяся ни изолированной, ни точкой сочленения. Далее, ребра любого простого цикла графа G также принадлежат только одному блоку. Отсюда, в частности, следует, что блоки графа разбивают его ребра и простые циклы на множества, которые можно рассматривать как множества ребер. В первых трех теоремах этой главы устанавливаются несколько эквивалентных условий, обеспечивающих существование у графа точки сочленения и моста и неразделимость графа. [18]
Мы думаем, что читателю будет полезно исследовать конструкцию насыщенного элементарного графа С, изображенного на рис. 5.3.2. Предлагаем также убедиться в том, что и при ином расчленении графа G окончательный перечень бикритических блоков графа G будет таким же, как и в случае рассмотренного нами расчленения. [19]
Теорема 111.16. Пусть С - связный граф, не являющийся графом-вершиной. Тогда каждый блок графа О содержит хотя бы одно ребро. [20]
Кроме скалярных и векторных ветвей граф содержит отдельные блоки. Согласно [10] блок графа характеризуется некоторым операторам, входными и выходными ветвями. [21]
Теорема 111.18. Пусть А и А2 - разные ребра графа С. Они принадлежат одному блоку графа О тогда и только тогда, когда оба они содержатся в некотором цикле графа С. [22]
Тогда Н содержится в некотором блоке графа О. Более того, если подграф Н отличен от графа-вершины, то он содержится ровно в одном блоке графа С. [23]
Обозначим через Н объединение всех тех блоков графа О, которые соответствуют вершинам подмножества V, лежащим в С. [24]
Тг совпадает с множеством ребер некоторого блока графа О. [25]
Далее, G, есть блок, a G - i таковым не является. Поскольку сам граф G - блок, то найдется максимально возможное j, такое, что d есть блок графа GJ. Рассмотрим ость PJ I. В зависимости от расположения концевых вершин этой ости возможны несколько случаев. [26]
Часто можно заметить, что связный граф с достаточно большим числом точек сочленения похож на дерево. Дерево блоков и точек сочленения графа G ( обозначение: be ( G)) представляет собой граф, у которого множество вершин есть объединение множества блоков и множества точек сочленения графа G и две вершины смежны, если одна из них соответствует блоку графа G, а другая - точке сочленения графа G, принадлежащей этому блоку. Легко показать, что если G - связный граф, то граф be ( G) действительно является деревом. [27]
 |
Граф, его граф блоков и его граф точек сочленения. [28] |
Известны несколько графов пересечений, получаемых из графа G, которые представляют его структуру. Блоки графа G соответствуют вершинам графа B ( G), и две вершины графа В ( G) смежны тогда и только тогда, когда соответствующие им блоки графа G имеют общую точку сочленения. Две вершины графа С ( G) смежны тогда и только тогда, когда соответствующие им точки сочленения графа G принадлежат одному блоку. Заметим, что C ( G) определяется только для графов G, имеющих хотя бы одну точку сочленения. [29]
Представим себе, что вершины графа изображают узлы некоторой информационной сети, а ребра соответствуют линиям передачи. Знание блоков графа также очень важно, если принять во внимание то, что многие графовые задачи, такие как нахождение всех элементарных циклов или установление факта планарно сти графа ( граф называется планарным, если его можно так начертить на плоскости, чтобы никакие два ребра не пересекались), приводят естественным путем к аналогичным задачам для блоков данного графа. [30]
Страницы: 1 2 3