Как построить дерево по коду

Алгоритм построения кода Прюфера по дереву

Вход: дерево с 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:

Источник

§ 3.2. Деревья и леса

Дерево – связный граф без циклов. Лес – произвольный граф без циклов.

Очевидно, связные компоненты леса являются деревьями. Необходимые и достаточные условия для графа “быть деревом” даёт следующая теорема.

Теорема. Связный граф является деревом в том и только том случае, если количества его вершин и рёбер связаны соотношением

Отметим ещё два свойства деревьев: 1) для любых вершин и дерева существует единственный путь из в 2) в любом дереве есть висячая вершина (если дерево имеет хотя бы одно ребро, то у него не менее двух висячих вершин).

Упражнение 3.12. Найти количество неизоморфных графов с 3 вершинами.

Решение. Если граф с 3 вершинами не имеет ни одного ребра, то он изоморфен Рассматривая далее случаи графов с 1, 2, 3 рёбрами, мы получим все неизоморфные графы с 3 вершинами – см. рис. 3.16. Их всего 4.

Упражнение 3.13. Найти все (с точностью до изоморфизма) связные графы с 4 вершинами.

Р ешение. Пусть – граф с 4 вершинами. Понятно, что если рёбер два или меньше, то несвязен. Следовательно, возможное количество рёбер – это 3, 4, 5, 6. Граф с 6 рёбрами – полный, он изоморфен графу Несложный перебор оставшихся вариантов показывает, что графов, удовлетворяющих требуемым условиям, ровно 6. Они изображены на рис. 3.17.

Упражнение 3.14. Найти все (с точностью до изоморфизма) деревья с 5 вершинами.

Решение. Пусть – дерево с 5 вершинами. Понятно, что возможны ровно 3 следующих случая: а) все степени вершин не превосходят 2; б) есть вершина степени 3; в) есть вершина степени 4. В каждом из этих случаев имеется по одному дереву – см. рисунок 3.18.

Существуют способы компактной записи (кодирования) деревьев. Из них мы рассмотрим два: двоичное (или бинарное) кодирование (т.е. составление кода из 0 и 1) и кодирование Прюфера (код из натуральных чисел).

П ри бинарном кодировании каждому дереву приписывается последовательность из 0 и 1 длины где – количество рёбер дерева. В этой последовательности ровно единиц и столько же нулей. Для составления кода представим себе, что граф представляет собой реку, по берегу которой мы совершаем её обход так, чтобы река оставалась всё время с одной стороны, для определённости будем считать, что слева. При проходе по ребру в первый раз в код записывается 0, а второй раз (по противоположному берегу) – пишется 1. На рисунке 3.19 показано на примере, как осуществляется бинарное кодирование.

Двоичное кодирование дерева неоднозначно. Оно зависит от выбора начала обхода, направления обхода, а также изображения дерева на плоскости. Далее, не всякая последовательность из единиц и нулей является бинарным кодом какого-нибудь дерева. Необходимое и достаточное условие существования дерева для данной двоичной последовательности даёт следующее утверждение.

Теорема. Пусть – последовательность, в которой нулей и единиц. Она является бинарным кодом некоторого дерева в том и только том случае, если в любом её начальном отрезке количество нулей не меньше количества единиц.

Например, последовательность 0011011100011 не является кодом никакого дерева (так как содержит начальный отрезок 00110111), а последовательность 00011010011011 является кодом дерева.

Декодирование (т.е. построение дерева по коду) можно осуществить, копируя процесс кодирования, т.е. восстанавливая “реку”, обход которой был совершён.

Упражнение 3.15. Построить дерево по его двоичному коду 00011010011011.

Решение показано на рисунке 3.20.

Для построения кода Прюфера вначале следует занумеровать вершины дерева натуральными числами (произвольным образом). Далее поступаем так. Берём висячую вершину с наименьшим номером. Пусть это будет вершина с номером Она инцидентна единственной вершине, которая имеет номер, скажем, Тогда записываем в код и удаляем вершину с ребром после чего возвращаемся к началу алгоритма. Это делается до тех пор, пока не останется одно ребро. Длина кода получается равной где – количество вершин дерева.

Упражнение 3.16. Построить код Прюфера дерева, изображённого на рисунке 3.21.

Р ешение. Применим описанный выше алгоритм (см. рисунок 3. 22):

1. висячая вершина с наименьшим номером – 2; пишем 1, удаляем вершину 2 и ребро (1,2);
2. висячая вершина – 1; пишем 3, удаляем вершину 1 и ребро (1,3);
3. висячая вершина – 5; пишем 4, удаляем вершину 5 и ребро (4,5);
4. висячая вершина – 4; пишем 3, удаляем вершину 4 и ребро (4,3).

Декодирование кода Прюфера осуществляется следующим образом. Пусть дан код где Нарисуем на плоскости точек, занумерованных числами пока не соединённые друг с другом рёбрами. Далее рисуем рёбра одно за другим согласно следующему правилу:

1. находим – наименьшее число из множества которого нет в последовательности соединяем ребром вершины и
2. находим – наименьшее число из множества не встречающееся в последовательности соединяем ребром вершины и
3. находим – наименьшее число из множества не встречающееся в последовательности соединяем ребром вершины и

находим – наименьшее число из множества не встречающееся в последовательности соединяем ребром вершины и

в последовательности отсутствуют ровно 2 числа из множества обозначим их и соединим соответствующие вершины.

Упражнение 3.17. Построить дерево по коду 1353.

Решение. Применим описанный выше алгоритм.

1. Так как длина кода равна 4, то дерево будет иметь 6 вершин. Нарисуем на плоскости точки 1,2,3,4,5,6.
2. Наименьшее число – это 2. Пишем его под 1:
3. Наименьшее число – это 1. Пишем его под 3:
4. Наименьшее число – это 4. Пишем его под 5:
5. Н аименьшее число – это 5. Пишем его под 3:
6. Отсутствуют в последовательности 2145 числа 3 и 6.

Таким образом, в графе будут следующие рёбра: (1,2), (3,1), (5,4), (3,5), (3,6). Искомое дерево изображено на рисунке 3.23.

Замечание. В отличие от бинарного кода код Прюфера определяется деревом однозначно, если зафиксирована нумерация вершин дерева. Назовём дерево с заданной на нём нумерацией вершин помеченным деревом. Кодирование Прюфера определяет взаимно однозначное соответствие между помеченными деревьями и их кодами. Следовательно, число помеченных деревьев с вершинами (обозначим это число ) равно числу их кодов. Кодом является произвольная последовательность чисел, взятых из множества Таким образом, мы имеем:

Формула (5) называется формулой Кэли.

Источник

3.10. Кодирование деревьев

Выделим в дереве какую-нибудь одну вершину, которую назовем корнем. Полученное дерево с выделенной вершиной называетсякорневым.

Для задания (с точностью до изоморфизма) корневыхдеревьев используюткод из 0 и 1, который мы определим индуктивно.

Определение.Кодом корневого дерева с одним ребром является .Пусть деревья и с корнямиa и b соответственно (см. рис.) имеют коды и .Тогда кодом дерева с корнем с является код , а кодом дерева с корнем — код.

Пример 1. Написать код дерева, изображенного на рисунке.

Итак, код дерева —.

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

Чтобы построить корневое дерево по кодуиз нулей и единиц, нужно разбить последовательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим слева неиспользованным нулем. Если образованные таким образом пары пометить снизу кода фигурными скобками, то каждая такая скобка будет соответствовать ребру графа.

Пример 2.Построить дерево по коду.

Для задания помеченныхдеревьев, т.е. деревьев, вершины которых занумерованы, используют код из натуральных чисел.

Пусть дано помеченное дерево. Чтобы построить его код из натуральных чисел действуем следующим образом. Находим висячую вершину с наименьшим номером. Записываем номер смежной с ней вершины (это начало кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Для полученного в результате данной операции дерева находим висячую вершину с наименьшим номером, записываем номер смежной с ней вершины (это продолжение кода), после чего удаляем эту висячую вершину вместе с инцидентным ей ребром. Так поступаем до тех пор, пока не останется последнее ребро.

Заметим, что длина кода из натуральных чисел на единицу меньше числа ребер и на две единицы меньше числа вершин данного дерева.

Пример 3.На рисунке изображено помеченное дерево. Его код.

Построение дерева по коду из натуральных чиселрассмотрим на примере кода. Прежде всего, заметим, что дерево, которое нам предстоит построить, имеет 8 вершин.

Источник