АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. FAST (Методика быстрого анализа решения)
  2. I Психологические принципы, задачи и функции социальной работы
  3. I. 1.1. Пример разработки модели задачи технического контроля
  4. I. 1.2. Общая постановка задачи линейного программирования
  5. I. 2.1. Графический метод решения задачи ЛП
  6. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  7. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  8. I. Значение и задачи учета. Основные документы от реализации продукции, работ, услуг.
  9. I. Иммунология. Определение, задачи, методы. История развитии иммунологии.
  10. I. Ситуационные задачи и тестовые задания.
  11. I. Цель и задачи дисциплины
  12. I.5.3. Подготовка данных для задачи линейного программирования

 

Задание. Построить дерево по его коду Прюфера 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}. Через ai обозначим i -й элемент кода. В частности a1 =7, a2 =1, a3 =5 и т.д. Будем выполнять цикл, на каждой итерации которого находится ребро дерево и удаляется элемент из множества B. На i-й итерации цикла, при i = 1, 2, …, m+1, минимальный элемент bÎB, среди не равных никакому из aj " j ≥ i, соединяется с ai и затем удаляется из 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).

 

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

 

1. M = [0, 1[, a = –1 16. M = Q, a = ½
2. M = [0, 1[, a = –2 17. M = [0, ½], a = –2
3. M = ]-1, 1[, a = –1 18. M = [0, 5], a = –1/5
4. M = {0, 1}, a = –1 19. M = N, a = 2
5. M = N, a = –1 20. M = R, a = – ½
6. M = R, a = 1 21. M = Q, a = – 1/3
7. M = [0, 1], a = –2 22. M = N, a = 0
8. M = Q, a = 2 23. M = ] –1,0], a = 1
9. M = R \ {1}, a = –1 24. M = ] –1,0], a = 2
10. M = R, a = 2 25. M = ] –1,0], a = 3/2
11. M = R, a = ½ 26. M = [0,1], a = – 3/2
12. M = R, a = – ½ 27. M = Q, a = ¾
13. M = N, a = –2 28. M = ] –1,0], a = 4/3
14. M = [0, 1[, a = – 1 29. M = R \ {1/2}, a = –2
15. M = Q, a = 0 30. M = [0, 1/3], a = –3

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)