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

15371 76412 26415 76421 16415 65413 36412 46715 16415 77411

15311 76422 26425 76431 16425 65423 36421 46725 16425 77421

11371 73412 22415 71421 13415 62413 31412 43715 12415 71411

Пример решения задачи 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. (Моноиды). Задано вещественное числои подмножествоMRмножества вещественных чисел. Будет лиMотносительно операцииx*y=x+y+xyмоноидом? Группой?

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