Деревья

30. Является ли дерево двудольным графом?

31. Код Прюфера нумерованного дерева с n вершинами состоит из последовательности n-2 чисел, принимающих значения от 1 до n. Упаковка. Код Прюфера нумерованного дерева с n вершинами строится следующим образом. В цикле находится висячая вершина с наименьшим номером. Номер вершины смежной с найденной записывается в последовательность. Цикл повторяется n-2 раза. Распаковка. Выписываем множество B={1, 2, 3, ∙ ∙ ∙, n}, где n = длина кода+2. Устанавливаем начальное множество ребер дерева T= Æ. Далее выполняются действия:

for (i=1; i<n-1; i++)

{

b= min { kÎB: k¹a_j " j ≥ i} ;

добавить к T ребро {b,a_i} ;

B = B \ {b} ;

}

Распаковать и упаковать следующие коды:

1. 4445577

2. 24446

3. 77321

4. 12579213

32. Найти число максимальных поддеревьев графа K₄ .

33. Найти все максимальные поддеревья графа, полученного удалением одного ребра из графа K₄ . Результат должен быть следующим: