81. Центры деревьев. Теорема.

Теорема. Центрами деревьев является вершина максимального типа и только она.Доказательство. Любая цепь l с началом в вершине V0(вершина максимального типа), проходит последовательно по вершинам уменьшающихся типов. Ее ребро V0V1 может привести вершину типа к, либо в вершину меньшего типа. Следующие ребра уже обязательно попадут в вершины меньшего типа. Таким образом, для L цепи l с началом в вершине типа к, имеем: l(L)k и , если вершина макс.типа единственная макс.удаленная от вершины макс.типа в дереве = ее типу к если (к-1).Рассмотрим случай, когда вершина V имеет не макс.тип. Покажем, что она начало более длинной цепи. Построим цепь lVV0, связыв.эту вершину с вершиной макс.типа. Если вершина V0- единственная вершина макс.типа , то она связанна с 2 вершинами типа (к-1). Можно построить цепь lV0V1 длины (к-1), не проходящую через последнее ребро цепи lVV0 и не имеющую с этой цепью общих вершин, иначе был бы цикл. Цепь l, которая явл.l(V2V1)и l(V1V0), если в дереве Д есть вершина V1 и V0 макс.типа, то можно построить связывающую их цепь. Если она проходит через другую вершину макс.типа, ее длина >2. Тогда V0 явл. началом цепи (к-1) с первым ребром V0V3, ведущим в вершину V3 типа (к-1). Эта цепь не имеет с построенной ранее цепью общих вершин , иначе был бы цикл. Длина цепи ≥(к+1).Для любой вершины не макс.типа и удаление (макс)>k. Дерево может иметь либо 1, либо и 2 центра.

85. Отношение достижимости. Базисный граф

Вершина V” ориентированного графа G наз. достижимой из V’, которая принадлежит G,если существует путь с началом в V’ и концом в V”. Отношение достижимости рефлексивно и транзитивно, поэтому с помощью этого отношения можно определить разбиение множества вершин на классы эквивалентности. V” и V’ принадлежат 1 классу эквивалентности, если они достижимы друг из друга. Пути L(V’…V”) и L(V”…V’) связывают эти вершины. Тогда композиция этих путей образует цикл, которого быть не должно. Если граф ациклический, то каждая вершина этого графа образует класс эквивалентности, состоящий из 1 этой вершины. Минимальны граф G, индуцирующий на множестве вершин V то же отношение достижимости, что и заданный ориентированный граф (граф с неуменьшаемым количеством ребер) наз. базисным. Если G-конечный граф, то базисный для него граф можно построить, причём для ациклического графа единственным образом.

88.Способы представления деревьев

Массив

В виде массива проще всего представляется полное бинарное дерево, так как оно всегда имеет строго определенное число вершин на каждом уровне. Вершины можно пронумеровать слева направо последовательно по уровням и использовать эти номера в качестве индексов в одномерном массиве.

Если число уровней дерева в процессе обработки не будет существенно изменяться, то такой способ представления полного бинарного дерева будет значительно более экономичным, чем любая списковая структура.

Однако далеко не все бинарные деревья являются полными. Для неполных бинарных деревьев применяют следующий способ представления. Бинарное дерево дополняется до полного дерева, вершины последовательно нумеруются. В массив заносятся только те вершины, которые были в исходном неполном дереве. При таком представлении элемент массива выделяется независимо от того, будет ли он содержать узел исходного дерева. Следовательно, необходимо отметить неиспользуемые элементы массива. Это можно сделать занесением специального значения в соответствующие элементы массива. В результате структура дерева переносится в одномерный массив. Адрес любой вершины в массиве вычисляется как адрес = 2к-1+i-1,

где k-номер уровня вершины, i- номер на уровне k в полном бинарном дереве. Адрес корня будет равен единице. Для любой вершины можно вычислить адреса левого и правого потомков

адрес_L = 2к+2(i-1)

адрес_R = 2к+2(i-1)+1

Главным недостатком рассмотренного способа представления бинарного дерева является то, что структура данных является статической. Размер массива выбирается исходя из максимально возможного количества уровней бинарного дерева. Причем чем менее полным является дерево, тем менее рационально используется память.

Список

Граф можно представить в виде списочной структуры, состоящей из списков двух типов √ списка вершин и списков ребер. Элемент списка вершин содержит поле данных и два указателя. Один указатель связывает данный элемент с элементом другой вершины. Другой указатель связывает элемент списка вершин со списком ребер, связанных с данной вершиной. Для ориентированного графа используют список дуг, исходящих из вершины. Элемент списка дуг состоит только из двух указателей. Первый указатель используется для того, чтобы показать в какую вершину дуга входит, а второй √ для связи элементов в списке дуг вершины.

71.Произведением графов G_i=(X_i,Г_i) называется граф G=(X,Г), где

X=X₁ X₂ ... X_n= {( x₁ x₂ ... x_n)/x_i X_i}

и

Г( x₁ x₂ ... x_n) = Г₁x₁  Г₂x₂ ... Г_nx_n

(все подсистемы одновременно изменяют свое состояние).

Произведение графов и определяется следующим образом. Множеством вершин графа является декартово произведение множеств и , то есть вершины этого графа - упорядоченные пары , где - вершина первого сомножителя, - вершина второго. Вершины и в смежны тогда и только тогда, если и смежна с в графе , или и смежна с в графе . С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух цепей дает прямоугольную решетку. Если один из сомножителей превратить в цикл, добавив одно ребро, то прямоугольная решетка превратится в цилиндрическую, а если и второй сомножитель превратить в цикл, то получится тороидальная решетка.