Пример решения задачи 5
Выполним распаковку кода Прюфера. С этой целью в верхней строке выпишем заданный код. Под этим кодом выпишем последовательность состоящую из чисел 1, 2, …, m+2, где m – длина кода:
Положим B=. Через 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 наименьший из среди не равных
равен b=2. Присоединяем ребро . Вычеркиваем 2 из верхней последовательности, и 7 – из нижней. B = B\ =.
При i=2 наименьший из среди не равных
равен b=6. Присоединяем ребро . Вычеркиваем 6 из верхней последовательности, и 1 – из нижней. B = B\ =.
При i=3 наименьший из среди не равных
равен b=1. Присоединяем ребро . Вычеркиваем 1 из верхней последовательности, и 5 – из нижней.B = B\ =.
При i=4 наименьший из среди не равных
равен b=5. Присоединяем ребро . Вычеркиваем 5 из верхней последовательности, и 4 – из нижней.B = B\ =.
При i=5 наименьший из среди не равных
равен b=4. Присоединяем ребро . Вычеркиваем 4 из верхней последовательности, и 3 – из нижней. B = B\ =.
Цикл закончился. Соединяем два оставшихся элемента 3 и 7.
Рис. 2. Дерево с кодом 71543
Сделаем проверку. С этой целью построим код для полученного дерева. Построение кода состоит из цикла, на каждой итерации которого удаляется висячая вершина с наименьшим номером и выписывается номер вершины, соединенной с висячей.
В данном случае удаляем 2 и выписываем 7. Затем удаляем 6 и выписываем 1. Затем удаляем 1 и выписываем 5. Удаляем 5 и выписываем 4. Удаляем 4 и выписываем 3. Цикл заканчивается, когда останется две вершины. В результате получаем код, состоящий из выписанных чисел 7, 1, 5, 4, 3. Этот код совпадает с заданным. Следовательно, дерево построено верно.
Задача 6. Моноиды
Задано вещественное число a и подмножество M Í R множества вещественных чисел. Будет ли M относительно операции x*y = x + y + axy моноидом? Группой? Ниже N = обозначает множество натуральных чисел, Q – множество рациональных дробей m/n (где m,n Î Z, n¹0).
| 1. M = [0, 1[, a = –1 | 19. M = Q, a = ½ |
| 2. M = [0, 1[, a = –2 | 20. M = [0, ½], a = –2 |
| 3. M = ]-1, 1[, a = –1 | 21. M = [0, 5], a = –1/5 |
| 4. M = , a = –1 | 22. M = N, a = 2 |
| 5. M = N, a = –1 | 23. M = R, a = – ½ |
| 6. M = R, a = 1 | 24. M = Q, a = – 1/3 |
| 7. M = [0, 1], a = –2 | 25. M = N, a = 0 |
| 8. M = Q, a = 2 | 26. M = ] –1,0], a = 1 |
| 9. M = R \ , a = –1 | 27. M = ] –1,0], a = 2 |
| 10. M = R, a = 2 | 28. M = ] –1,0], a = 3/2 |
| 11. M = R, a = ½ | 29. M = [0,1], a = – 3/2 |
| 12. M = R, a = – ½ | 30. M = Q, a = ¾ |
| 13. M = N, a = –2 | 31. M = ] –1,0], a = 4/3 |
| 14. M = [0, 1[, a = – 1 | 32. M = R \ , a = –2 |
| 15. M = Q, a = 0 | 33. M = [0, 1/3], a = –3 |
| 16. M = R, a = – 1 | 34. M = [0,1], a = – 4/3 |
| 17. M = [0, 1], a = – 3/2 | 35. M = Q, a = 5/6 |
| 18. M = Q, a = – 1 | 36. M = R \ , a = — 6/5 |
Пример решения задачи 6.
Будет ли множество M = [0,1] с операцией x*y = x+y – (9/8)xy полугруппой? Моноидом? Группой?
1) Проверим, будет ли x*yÎM при x,y ÎM. Это выполнено если для всех удовлетворяющих неравенствам 0£x, y£1 чисел x, y будет иметь место 0£x*y£1. Рассмотрим произвольный 0£y£1. Функция f(x)= x+y – (9/8)xy при фиксированном y будет линейной по x. На концах интервала [0,1] она принимает значения f(0)=y и f(1)=1-(1/8)y. Поскольку эти значения лежат в интервале [0,1], то значения этой функции во внутренних точках интервала принадлежат [0,1]. Отсюда для всех x,y Î M значения x*y принадлежат M.
2) Проверим ассоциативность (x*y)*z=x*(y*z). С этой целью раскроем обе части проверяемого равенства:
Поскольку последнее равенство имеет место, то операция * ассоциативна. Стало быть, (M,*) – полугруппа.
3) Проверим, будет ли (M,*) моноидом. Напомним, что моноидом называется полугруппа M, в которой существует элемент eÎM, удовлетворяющий для всех xÎM соотношениям x*e = e*x = x.
Этот элемент eÎM называется нейтральным. Для нахождения нейтрального элемента получаем тождество x+e –(9/8)xe = x, которое должно быть выполнено для всех xÎM. Легко видеть, что e=0 удовлетворяет этому тождеству. Отсюда вытекает, что (M,*) – моноид.
4) Проверим, будет ли (M,*) группой. Напомним, что моноид (M,*) называется группой, если для каждого x Î M найдется такой y Î M, что x*y = e. Отсюда данный моноид будет группой, если и только если для каждого xÎ M существует yÎM, удовлетворяющий уравнению x+y-(9/8)xy = 0. Находим y = -x/(1-(9/8)x). Отсюда для x=8/9 это уравнение не имеет решений. Стало быть, заданный моноид не является группой.
Ответ: (M,*) является полугруппой, моноидом, но не является группой
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник
Алгоритм построения кода Прюфера по дереву
Вход: дерево с n вершинами.
Выход: код Прюфера длины n – 2.
Выбрать вершину v – лист дерева с наименьшим номером;
Добавить номер единственного соседа v в последовательность кода Прюфера;
Удалить вершину v из дерева;
Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.
Алгоритм составления дерева по коду:
1.Выписываем висячие вершины, всего вершин на 2 больше чем значений в коде дерева.
2. находим наименьшее натуральное число, которое не встречается в последовательности.
3. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.
4. находим следующее число.
Рассмотрим применение данного алгоритма на примере.
Пример 1. Постройте дерево, которому соответствует код
1. Выписываем висячие вершины. Всего вершин на 2 больше чем значений в коде дерева, в данном случае такими будут 3,4,5,6,7.
2. Вершину с минимальным номером (3) соединяем с первым значением кода (1).
3. Поскольку вершина (1) еще встречается в коде , то соединяем следующую висячую вершину (4) с вершиной из кода (2).
Дальше вершины (2) больше нет в коде, потому она становится висячей с наименьшим номером, потому следующим шагом я соединяю ее (2) со следующим значением кода (1).
Далее 6 – 7. Код закончился, осталась 6. Соединяем ее с 1.
Пример 2. Построить дерево по к . Смотреть решение »
Задана матрица инцидентности неориентированного графа G:
Источник
Алгоритм построения кода Прюфера по дереву
Вход: дерево с n вершинами.
Выход: код Прюфера длины n – 2.
Выбрать вершину v – лист дерева с наименьшим номером;
Добавить номер единственного соседа v в последовательность кода Прюфера;
Удалить вершину v из дерева;
Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.
Алгоритм составления дерева по коду:
1.Выписываем висячие вершины, всего вершин на 2 больше чем значений в коде дерева.
2. находим наименьшее натуральное число, которое не встречается в последовательности.
3. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.
4. находим следующее число.
Рассмотрим применение данного алгоритма на примере.
Пример 1. Постройте дерево, которому соответствует код
1. Выписываем висячие вершины. Всего вершин на 2 больше чем значений в коде дерева, в данном случае такими будут 3,4,5,6,7.
2. Вершину с минимальным номером (3) соединяем с первым значением кода (1).
3. Поскольку вершина (1) еще встречается в коде , то соединяем следующую висячую вершину (4) с вершиной из кода (2).
Дальше вершины (2) больше нет в коде, потому она становится висячей с наименьшим номером, потому следующим шагом я соединяю ее (2) со следующим значением кода (1).
Далее 6 – 7. Код закончился, осталась 6. Соединяем ее с 1.
Пример 2. Построить дерево по к . Смотреть решение »
Решение задач линейного программирования графическим методом
Задача. Решить графически задачу линейного программирования, определив экстремальное значение целевой функции:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение 3x1+x2 = 9 по двум точкам.
Для нахождения первой точки . Смотреть решение »
Категория: Линейное программирование | Просмотров: 13671 | Добавил: Admin | Дата: 08.02.2015 | Комментарии (0)
Источник
3.10. Кодирование деревьев
Выделим в дереве какую-нибудь одну вершину, которую назовем корнем. Полученное дерево с выделенной вершиной называетсякорневым.
Для задания (с точностью до изоморфизма) корневыхдеревьев используюткод из 0 и 1, который мы определим индуктивно.
О
пределение.Кодом корневого дерева с одним ребром является 
.Пусть деревья 
и 
с корнямиa и b соответственно (см. рис.) имеют коды 
и 
.Тогда кодом дерева 
с корнем с является код 
, а кодом дерева 
с корнем 
— код
.
Пример 1. Написать код дерева, изображенного на рисунке.
И
так, код дерева —
.
Справедливо следующее утверждение:для того, чтобы последовательность нулей и единиц являлась кодом некоторого дерева необходимо и достаточно, чтобы число нулей и единиц в этой последовательности было одинаковым, причем в любом начальном отрезке последовательности количество нулей было не меньше количества единиц.
Чтобы построить корневое дерево по кодуиз нулей и единиц, нужно разбить последовательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем. Если образованные таким образом пары пометить снизу кода фигурными скобками, то каждая такая скобка будет соответствовать ребру графа.
П
ример 2.Построить дерево по коду
.
Для задания помеченныхдеревьев, т.е. деревьев, вершины которых занумерованы, используют код из натуральных чисел.
Пусть дано помеченное дерево. Чтобы построить его код из натуральных чисел действуем следующим образом. Находим висячую вершину с наименьшим номером. Записываем номер смежной с ней вершины (это начало кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Для полученного в результате данной операции дерева находим висячую вершину с наименьшим номером, записываем номер смежной с ней вершины (это продолжение кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Так поступаем до тех пор, пока не останется последнее ребро.
Заметим, что длина кода из натуральных чисел на единицу меньше числа ребер и на две единицы меньше числа вершин данного дерева.
П
ример 3.На рисунке изображено помеченное дерево. Его код
.
Построение дерева по коду из натуральных чиселрассмотрим на примере кода. Прежде всего, заметим, что дерево, которое нам предстоит построить, имеет 8 вершин.
Источник