Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.
Определение. Построение кода Прюфера для заданного дерева
Код Прюфера – это способ взаимно однозначного кодирования помеченных деревьев с n вершинами с помощью последовательности n-2 целых чисел в отрезке [1,n]. То есть, можно сказать, что код Прюфера – это биекция между всеми остовными деревьями полного графа и числовыми последовательностями.
Данный способ кодирования деревьев был предложен немецким математиком Хайнцом Прюфером в 1918 году.
Рассмотрим алгоритм построения кода Прюфера для заданного дерева с n вершинами.
На вход подается список ребер. Выбирается лист дерева с наименьшим номером, затем он удаляется из дерева, и к коду Прюфера добавляется номер вершины, которая была связана с этим листом. Эта процедура повторяется n-2 раза. В конце концов, в дереве останется только 2 вершины, и алгоритм на этом завершается. Номера оставшихся двух вершин в код не записываются.
Таким образом, код Прюфера для заданного дерева – это последовательность из n-2 чисел, где каждое число – номер вершины, связанной с наименьшим на тот момент листом – то есть это число в отрезке [1,n].
Пример Исходное дерево Код Прюфера: 1 Код Прюфера: 1 5 Код Прюфера: 1 5 2 Код Прюфера: 1 5 2 6 Код Прюфера: 1 5 2 6 6 Код Прюфера: 1 5 2 6 6 2 Код Прюфера: 1 5 2 6 6 2 1 Код Прюфера: 1 5 2 6 6 2 1 3
Восстановление дерева по его коду Прюфера
Рядом с задачей построения кода Прюфера стоит задача восстановления закодированного дерева. Будем рассматривать алгоритм восстановления дерева со следующими условиями: на вход подается последовательность цифр (вершин), которая представляет код Прюфера, результатом будет список ребер дерева. Таким образом, задача будет решена.
Рассмотрим алгоритм декодирования подробно. Помимо кода нам нужен список всех вершин графа. Мы знаем, что код Прюфера состоит из n-2 вершин, где n – это число вершин в графе. То есть, мы можем по размеру кода определить число вершин в закодированном дереве.
В результате, в начале работы алгоритма мы имеем массив из кода Прюфера размера n-2 и массив всех вершин графа: [1… n]. Далее n-2 раза повторяется такая процедура: берется первый элемент массива, содержащего код Прюфера, и в массиве с вершинами дерева производится поиск наименьшей вершины, не содержащейся в массиве с кодом. Найденная вершина и текущий элемент массива с кодом Прюфера составляют ребро дерева. Данные вершины удаляются из соответствующих массивов, и описанная выше процедура повторяется, пока в массиве с кодом не закончатся элементы. В конце работы алгоритма в массиве с вершинами графа останется две вершины, они составляют последнее ребро дерева. В результате получаем список всех ребер графа, который был закодирован.
Пример Восстановим дерево по коду Прюфера, который был получен в примере кодирования.
Первый шаг Код Прюфера: 1 5 2 6 6 2 1 3 Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 4 Список ребер: 1 4
Второй шаг Код Прюфера: 1 5 2 6 6 2 1 3 Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 7 Список ребер: 1 4, 5 7
Третий шаг Код Прюфера: 1 5 2 6 6 2 1 3 Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 5 Список ребер: 1 4, 5 7, 2 5
Четвертый шаг Код Прюфера: 1 52 6 6 2 1 3 Массив вершин дерева: 1 2 3 456 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 8 Список ребер: 1 4, 5 7, 2 5, 6 8
Пятый шаг Код Прюфера: 1 526 6 2 1 3 Массив вершин дерева: 1 2 3 456 78 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 9 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9
Шестой шаг Код Прюфера: 1 5266 2 1 3 Массив вершин дерева: 1 2 3 456 789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 6 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6
Седьмой шаг Код Прюфера: 1 52662 1 3 Массив вершин дерева: 1 2 3 456789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 2 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2
Восьмой шаг Код Прюфера: 1 526621 3 Массив вершин дерева: 1 2 3 456789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 1 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1
Завершение алгоритма Код Прюфера: 1 5266213 Массив вершин дерева: 12 3 456789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 1 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1, 3 10
Заключение
Код Прюфера был предложен как наглядное и простое доказательство формулы Кэли о числе помеченных деревьев. На практике же его используют чаще для решения комбинаторных задач.
Немного разнообразим посты в мой жж алгоритмами, структурами данных и решением олимпиадных задач. Собственно озадачившись сабжем я не смог найти хорошо описанный алгоритм восстановления дерева на русском языке с примером.
Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.
Определение. Построение кода Прюфера для заданного дерева
Код Прюфера – это способ взаимно однозначного кодирования помеченных деревьев с n вершинами с помощью последовательности n-2 целых чисел в отрезке [1,n]. То есть, можно сказать, что код Прюфера – это биекция между всеми остовными деревьями полного графа и числовыми последовательностями.
Данный способ кодирования деревьев был предложен немецким математиком Хайнцом Прюфером в 1918 году.
Рассмотрим алгоритм построения кода Прюфера для заданного дерева с n вершинами.
На вход подается список ребер. Выбирается лист дерева с наименьшим номером, затем он удаляется из дерева, и к коду Прюфера добавляется номер вершины, которая была связана с этим листом. Эта процедура повторяется n-2 раза. В конце концов, в дереве останется только 2 вершины, и алгоритм на этом завершается. Номера оставшихся двух вершин в код не записываются.
Таким образом, код Прюфера для заданного дерева – это последовательность из n-2 чисел, где каждое число – номер вершины, связанной с наименьшим на тот момент листом – то есть это число в отрезке [1,n].
Пример Исходное дерево Код Прюфера: 1 Код Прюфера: 1 5 Код Прюфера: 1 5 2 Код Прюфера: 1 5 2 6 Код Прюфера: 1 5 2 6 6 Код Прюфера: 1 5 2 6 6 2 Код Прюфера: 1 5 2 6 6 2 1 Код Прюфера: 1 5 2 6 6 2 1 3
Восстановление дерева по его коду Прюфера
Рядом с задачей построения кода Прюфера стоит задача восстановления закодированного дерева. Будем рассматривать алгоритм восстановления дерева со следующими условиями: на вход подается последовательность цифр (вершин), которая представляет код Прюфера, результатом будет список ребер дерева. Таким образом, задача будет решена.
Рассмотрим алгоритм декодирования подробно. Помимо кода нам нужен список всех вершин графа. Мы знаем, что код Прюфера состоит из n-2 вершин, где n – это число вершин в графе. То есть, мы можем по размеру кода определить число вершин в закодированном дереве.
В результате, в начале работы алгоритма мы имеем массив из кода Прюфера размера n-2 и массив всех вершин графа: [1… n]. Далее n-2 раза повторяется такая процедура: берется первый элемент массива, содержащего код Прюфера, и в массиве с вершинами дерева производится поиск наименьшей вершины, не содержащейся в массиве с кодом. Найденная вершина и текущий элемент массива с кодом Прюфера составляют ребро дерева. Данные вершины удаляются из соответствующих массивов, и описанная выше процедура повторяется, пока в массиве с кодом не закончатся элементы. В конце работы алгоритма в массиве с вершинами графа останется две вершины, они составляют последнее ребро дерева. В результате получаем список всех ребер графа, который был закодирован.
Пример Восстановим дерево по коду Прюфера, который был получен в примере кодирования.
Первый шаг Код Прюфера: 1 5 2 6 6 2 1 3 Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 4 Список ребер: 1 4
Второй шаг Код Прюфера: 1 5 2 6 6 2 1 3 Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 7 Список ребер: 1 4, 5 7
Третий шаг Код Прюфера: 1 5 2 6 6 2 1 3 Массив вершин дерева: 1 2 3 4 5 6 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 5 Список ребер: 1 4, 5 7, 2 5
Четвертый шаг Код Прюфера: 1 52 6 6 2 1 3 Массив вершин дерева: 1 2 3 456 7 8 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 8 Список ребер: 1 4, 5 7, 2 5, 6 8
Пятый шаг Код Прюфера: 1 526 6 2 1 3 Массив вершин дерева: 1 2 3 456 78 9 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 9 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9
Шестой шаг Код Прюфера: 1 5266 2 1 3 Массив вершин дерева: 1 2 3 456 789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 6 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6
Седьмой шаг Код Прюфера: 1 52662 1 3 Массив вершин дерева: 1 2 3 456789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 2 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2
Восьмой шаг Код Прюфера: 1 526621 3 Массив вершин дерева: 1 2 3 456789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 1 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1
Завершение алгоритма Код Прюфера: 1 5266213 Массив вершин дерева: 12 3 456789 10 Минимальная вершина, не содержащаяся в коде Прюфера – это 1 Список ребер: 1 4, 5 7, 2 5, 6 8, 6 9, 2 6, 1 2, 3 1, 3 10
Заключение
Код Прюфера был предложен как наглядное и простое доказательство формулы Кэли о числе помеченных деревьев. На практике же его используют чаще для решения комбинаторных задач.
Выбрать вершину v – лист дерева с наименьшим номером;
Добавить номер единственного соседа v в последовательность кода Прюфера;
Удалить вершину v из дерева;
Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.
Алгоритм составления дерева по коду:
1.Выписываем висячие вершины, всего вершин на 2 больше чем значений в коде дерева.
2. находим наименьшее натуральное число, которое не встречается в последовательности.
3. это число – номер вершины, которую необходимо соединить с вершиной, которая встречается первой в коде.
4. находим следующее число.
Рассмотрим применение данного алгоритма на примере.
Пример 1.Постройте дерево, которому соответствует код
1. Выписываем висячие вершины. Всего вершин на 2 больше чем значений в коде дерева, в данном случае такими будут 3,4,5,6,7.
2. Вершину с минимальным номером (3) соединяем с первым значением кода (1).
Дальше вершины (2) больше нет в коде, потому она становится висячей с наименьшим номером, потому следующим шагом я соединяю ее (2) со следующим значением кода (1).
Далее 6 – 7. Код закончился, осталась 6. Соединяем ее с 1.
Задана матрица инцидентности неориентированного графа G:
Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
«МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ» (ФГБОУ ВПО МГГУ)
Факультет физико-математического образования, информатики и программирования
Кафедра прикладной математики и математических методов в экономике
По Дискретной математике
На тему: Код Прюфера
Выполнил студент: Ежов А.В.
Группы ББИ 1-го курса Заочной формы обучения
Преподаватель: Большакова Наталья Сергеевна
Ст. преподаватель кф. ПМ и ММэ
Создать псевдоорграф с множеством вершин и 15 рёбрами, построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдографа построить матрицу соседства вершин.
Для соотнесенного псевдографа построить матрицу соседства вершин:
С помощью алгоритма Прюфера восстановить по вектору дерево:
Вершины <2, 4, 6>являются висячими.
Вершины 1, 3 есть в коде, они отмечены красным. Поэтому вершину 1 соединяем с вершиной 4.
Закодируем существующее дерево в код Прюфера. Если решение правильно, то коды должны совпасть.
1. Найти висячую вершину с минимальным номером i.
2. Записать в код Прюфера вершину, смежную с i.
3. Удалить вершину i из дерева. Если дерево не пустое, то перейти к п.1.
Находим висячую вершину с минимальным номером. Минимальный номер 2, удаляем ребро соединяющую вершины 2 и 5, записываем в код 5.
Теперь, висячая вершина с минимальным номером 4. Удаляем ребро между вершинами 4 и 1. Добавляем в код 1.
1 убираем, 3 добавляем. Получается (5, 1, 3). Действие повторяем до тех пор, пока останется одно ребро с конечной вершиной. Результат кода сравним с первоначальным кодом.
(5, 1, 3, 5, 7, 8, 9, 10) = (5,1,3,5,7,8,9,10)
Коды равны, следовательно, решение было правильным.
псевдограф матрица диаграмма прюфер
Для функции построить таблицу истинности, СДНФ и СКНФ.
Для построения СКНФ необходимо произвести следующие действия:
1. Выбрать все строки из таблицы истинности, в которых значение функции равняется 0.
3. Объединить получившиеся ЭД конъюнкцией.
1. Выбираем 7 строку таблицы истинности, т.к. значение функции в этой строке равно 0.
2. По правилам, получаем следующую ЭД: ¬x V ¬y V z
3. Т.к. ЭД всего одна, то она и будет СКНФ
Для построения СДНФ необходимо произвести следующие действия:
1. Выбрать все строки из таблицы истинности, в которых значение функции равняется 1.
3. Объединить получившиеся ЭК дизъюнкцией.
2. По правилам получаем следующие ЭК:
3. Объединяем получившиеся конъюнкции дизъюнкцией и получаем СДНФ:
Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
лабораторная работа [85,5 K], добавлен 09.01.2009
Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.
контрольная работа [463,0 K], добавлен 17.05.2015
Теоретико-множественная и геометрическая форма определения графов. Матрица смежностей вершин неориентированного и ориентированного графа. Элементы матрицы и их сумма. Свойства матрицы инцидентности и зависимость между ними. Подмножество столбцов.
реферат [81,0 K], добавлен 23.11.2008
Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
контрольная работа [335,2 K], добавлен 05.07.2014
Понятие обратной матрицы. Пошаговое определение обратной матрицы: проверка существования квадратной и обратной матрицы, расчет определителя и алгебраического дополнения, получение единичной матрицы. Пример расчета обратной матрицы согласно алгоритма.
презентация [54,8 K], добавлен 21.09.2013
Поиск собственных чисел и построение фундаментальной системы решений. Исследование зависимости жордановой формы матрицы А от свойств матрицы системы. Построение фундаментальной матрицы решений методом Эйлера, решение задачи Коши и построение графиков.
курсовая работа [354,7 K], добавлен 14.10.2010
Вычисление и построение матрицы алгебраических дополнений. Решение системы линейных уравнений по формулам Крамера, с помощью обратной матрицы и методом Гаусса. Определение главной и проверка обратной матрицы. Аналитическая геометрия на плоскости.
контрольная работа [126,9 K], добавлен 20.04.2016
Построение таблицы истинности. Доказательство истинности заключения путём построения дерева доказательства или методом резолюции. Выполнение различных бинарных операций. Построение графа вывода пустой резольвенты. Основные правила исчисления предикатов.
курсовая работа [50,7 K], добавлен 28.05.2015
реферат [87,2 K], добавлен 01.08.2009
Определение количества способов, которыми можно выбрать трех дежурных из группы в 20 человек. Построение таблицы истинности без предварительного упрощения функции по данному логическому выражению. Упрощение логических выражений с помощью карты Карно.
pyjioh
Восстановление структуры дерева из кода Прюфера.
