Блок - граф
Cтраница 1
Блок графа С, будучи связным подграфом, содержится в некоторой компоненте С графа О ( см. теорему 1.24) и, очевидно, является блоком этой компоненты. [1]
Блоки графа О обозначены большими буквами, а точки сочленения - малыми. [2]
Если блоки графа О планарны, то, используя достаточное число раз конструкцию теоремы XI. [3]
Теорема 111.14. Блоки графа О являются блоками его компонент. [4]
Тогда всякий блок графа О является блоком одного из подграфов Н или К. [5]
Если В - единственный блок графа С, содержащий х, то теорема, очевидно, справедлива. Тогда х инцидентна некоторому ребру А графа О, принадлежащему блоку В и не принадлежащему блоку В ( см. теорему III. Следовательно -, компонента Я подграфа 0: ( Е ( 0) - Е ( В)), содержащая х, отлична от графа-вершины. [6]
Сначала предположим, что О - Т - блок графа О. [7]
Ясно, что с точностью до вершинного изоморфизма блоки графа С, отличные от В, являются блоками графов 0 А и С А. [8]
Если несколько дуг с меткой х входят в один блок графа микропрограммы, то все они отмечаются одинаковым символом состояния. [9]
Покажем теперь, как нахождение отделимых ветвей обхода влечет за собой выделение блоков графа G. Тогда множество внутренних вершин соответствующей ветви блоков есть Fu, п оно может быть найдено как множество вершин, встретившихся в обходе не ранее, чем вершина у. Для того чтобы в момент нахождения ветви блоков выделить множество вершин корневого блока, достаточно при нахождении каждой ветви блоков множество ее внутренних вершин исключать из дальнейшего рассмотрения. Тогда к завершению обхода любой ветви блоков G все подветви, висящие на корневом Ълоке В, будут обойдены, а их внутренние вершины исключены. Останутся лишь вершины из В. [10]
Граф блоков данного графа G, обозначаемый В ( G), имеет своими вершинами блоки графа G и две вершины в нем смежны. [11]
 |
Граф, его граф блоков и его граф точек сочленения. [12] |
Теорема 3.5. Граф Н является графом блоков некоторого графа тогда и только тогда, когда каждый блок графа Н - полный граф. [13]
Ясно, что с точностью до вершинного изоморфизма блоки графа С, отличные от В, являются блоками графов 0 А и С А. [14]
Этот результат следует из теоремы 111.31. Графами Н являются графы / Ай, такие, что В - блоки графа О А. [15]
Страницы: 1 2 3