Пример решения задачи 6

Задание. Построить дерево по его коду Прюфера 71543 и сделать проверку.

Решение. Выполним распаковку кода Прюфера. С этой целью в верхней строке выпишем заданный код. Под этим кодом выпишем последовательность состоящую из чисел 1, 2, …, m+2, где m – длина кода:

1, 2, 3, 4, 5, 6, 7

7, 1, 5, 4, 3

Положим B={1, 2, 3, 4, 5, 6, 7}. Через a_i обозначим i -й элемент кода. В частности a₁ =7, a₂ =1, a₃ =5 и т.д. Будем выполнять цикл, на каждой итерации которого находится ребро дерево и удаляется элемент из множества B. На i-й итерации цикла, при i = 1, 2, …, m+1, минимальный элемент bÎB, среди не равных никакому из a_j " j ≥ i, соединяется с a_i и затем удаляется из B. Цикл выполняется для i=1, 2, 3, 4, 5. В нашей задаче

При i =1 наименьший из {1, 2, 3, 4, 5, 6, 7} среди не равных {7,1,5,4,3} равен b =2. Присоединяем ребро {7,2}. Вычеркиваем 2 из верхней последовательности, и 7 – из нижней. B = B \{2} ={1, 3, 4, 5, 6, 7}.

При i =2 наименьший из {1, 3, 4, 5, 6, 7} среди не равных {1,5,4,3} равен b =6. Присоединяем ребро {1,6}. Вычеркиваем 6 из верхней последовательности, и 1 – из нижней. B = B \{6} ={1, 3, 4, 5, 7}.

При i =3 наименьший из {1, 3, 4, 5, 7} среди не равных {5,4,3} равен b =1. Присоединяем ребро {5,1}. Вычеркиваем 1 из верхней последовательности, и 5 – из нижней.

B = B \{1} ={3, 4, 5, 7}.

При i =4 наименьший из {3, 4, 5, 7} среди не равных {4,3} равен b =5. Присоединяем ребро {4,5}. Вычеркиваем 5 из верхней последовательности, и 4 – из нижней.

B = B \{5} ={3, 4, 7}.

При i =5 наименьший из {3, 4, 7} среди не равных {3} равен b =4. Присоединяем ребро {3,4}. Вычеркиваем 4 из верхней последовательности, и 3 – из нижней. B = B \{4} ={3, 7}.

Цикл закончился. Соединяем два оставшихся элемента 3 и 7. Полученное дерево, приведенное на рис. 7.1, состоит из ребер {7,2}, {1,6}, {5,1}, {4,5}, {3,4}, {3,7}.

Рис. 7.1. Дерево с кодом Прюфера 71543

Сделаем проверку. С этой целью построим код для полученного дерева. Построение кода состоит из цикла, на каждой итерации которого удаляется висячая вершина с наименьшим номером и выписывается номер вершины, соединенной с висячей.

В данном случае удаляем 2 и выписываем 7. Затем удаляем 6 и выписываем 1. Затем удаляем 1 и выписываем 5. Удаляем 5 и выписываем 4. Удаляем 4 и выписываем 3. Цикл заканчивается, когда останется две вершины. В результате получаем код, состоящий из выписанных чисел 7, 1, 5, 4, 3. Этот код совпадает с заданным. Следовательно, дерево построено верно.

Ответ: Дерево состоит из ребер {7,2}, {1,6}, {5,1}, {4,5}, {3,4}, {3,7}.

Задача 7. (Моноиды). Задано вещественное число a и подмножество M Í R множества вещественных чисел. Будет ли M относительно операции x*y = x + y + axy моноидом? Группой?

Ниже N = {0,1,2,...} обозначает множество натуральных чисел, Q – множество рациональных дробей m/n (где m,n Î Z, n ¹0).

Варианты заданий

Поиск по сайту: