Блок - граф
Cтраница 3
Более того, каждое ребро принадлежит только одному блоку графа С. [31]
Этот перечень нужен для нахождения числа ребер и вершин в графе О. И) связных остовных подграфов графа О с множеством блоков II является восстанавливаемой характеристикой. Очевидно, что п ( 11 1, если И есть действительно перечень блоков графа О, и п ( 6) 0 в ином случае. Таким образом, перечень блоков графа О восстанавливаем. [32]
Тогда Н содержится в некотором блоке графа О. Более того, если подграф Н отличен от графа-вершины, то он содержится ровно в одном блоке графа С. [33]
Для нахождения производных используется сопряженный граф. Метод сопряженного графа и его математическое обоснование рассмотрены в работе [ 123, с. Расчет сопряженного графа также сводится к решению некоторой системы уравнений типа ( VIII29), но в данном случае она линейна, поскольку все блоки графа линейны по соответствующим переменным. [34]
 |
Граф, его граф блоков и его граф точек сочленения. [35] |
Известны несколько графов пересечений, получаемых из графа G, которые представляют его структуру. Блоки графа G соответствуют вершинам графа B ( G), и две вершины графа В ( G) смежны тогда и только тогда, когда соответствующие им блоки графа G имеют общую точку сочленения. Две вершины графа С ( G) смежны тогда и только тогда, когда соответствующие им точки сочленения графа G принадлежат одному блоку. Заметим, что C ( G) определяется только для графов G, имеющих хотя бы одну точку сочленения. [36]
Этот перечень нужен для нахождения числа ребер и вершин в графе О. И) связных остовных подграфов графа О с множеством блоков II является восстанавливаемой характеристикой. Очевидно, что п ( 11 1, если И есть действительно перечень блоков графа О, и п ( 6) 0 в ином случае. Таким образом, перечень блоков графа О восстанавливаем. [37]
На рис. 3.1 v - точка сочленения, a w нет, х - мост, а у нет; отдельно приведены четыре блока графа G. Каждое ребро графа принадлежит точно одному из его блоков, так же как и каждая вершина, не являющаяся ни изолированной, ни точкой сочленения. Далее, ребра любого простого цикла графа G также принадлежат только одному блоку. Отсюда, в частности, следует, что блоки графа разбивают его ребра и простые циклы на множества, которые можно рассматривать как множества ребер. В первых трех теоремах этой главы устанавливаются несколько эквивалентных условий, обеспечивающих существование у графа точки сочленения и моста и неразделимость графа. [38]
 |
Микропрограмма ( а и граф автомата Мили ( б, интерпретирующего микропрограмму. [39] |
Переход от микропрограммы к автомату Мили иллюстрируется на рис. 8.10, на котором показаны рассмотренный выше граф микропрограммы и граф автомата Мили, интерпретирующего ее. Исключение составляют дуги, идущие к конечной или к начальной вершине, которые не отмечаются. Если несколько дуг с меткой X входят в один блок графа микропрограммы, то все они отмечаются одинаковым символом состояния. [40]
А есть звено графа О. Предположим, что оба графа ОА и ОА не двусвязны. ОА не существует блока, содержащего обе вершины х и у. Обращаясь к теореме 111.32, видим, что каждый из графов ( Я) л связен ( в силу теоремы III. Из теорем 111.5 и 111.12 следует, что указанный цикл содержится в некотором блоке графа ОА и обе вершины х и у принадлежат этому блоку. [41]
Доказательство проводится методом индукции по числу блоков этой компоненты. Если компонента связности не содержит точек сочленения, то нетрудно отметить, что вызов ДВУСВ ( у 0) приводит к засылке в стек всех ребер этой компоненты, а затем ( см. цикл 10) запись этих ребер. Предположим теперь, что наша компонента содержит k 1 блоков и что алгоритм работает корректно для произвольной компоненты, содержащей менее k блоков. Согласно нашим предыдущим рассуждениям это неравенство означает, что v - корень или точка сочленения. Модифицированная таким образом компонента имеет k - 1 блок, и выполненение для нее процедуры ДВУСВ ( и 0) вызывает в силу индуктивного предположения корректную запись этих блоков. Действия алгоритма для модифицированной компоненты отличаются от действий в случае с исходной компонентой только тем, что для первой встреченной точки сочленения ( исходной компоненты) v цикл 4 не выполняется для вершин и, принадлежащих удаленному блоку. Отсюда легко следует, что ДВУСВ 0) корректно определяет все k блоков нашей компоненты связности, а тем самым весь алгоритм корректно определяет все блоки графа. [42]
Страницы: 1 2 3