3 группа/

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

дерево :D

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

Свойства :P

Свойство 1. :-*

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

Свойство 2. ;)

Всякое ребро в дереве является мостом. Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева. Это легко видеть на рисунке, если удалить, например, ребро А5А6 или ребро А1А3, или ребро А4А10 (оставив «вторым деревом» вершину A10).

Теорема :)

Теорема. Дерево с n вершинами имеет n-1 ребро

Кодирование Прюфера :(

Кодирование Прюфера (H. Prufer, 1918) переводит помеченные деревья порядка n в последовательности чисел по следующему алгоритму:

  1. Выбирается лист с минимальным номером.
  2. Лист и инцидентное ребро удаляются из дерева, в последовательность Прюфера добавляется номер смежной вершины.
  3. Если в дереве больше двух вершин, то п. 1, иначе — выход.

распаковка дерева =\

Распаковка дерева осуществляется по следующему алгоритму: Обозначим A = [a1, a2, ..., an-2] — последовательность Прюфера, N = [1, 2, ..., n].

  1. Выберем минимальное число v из N, не содержащееся в A.
  2. Соединяем ребром вершину с номером v и вершину, соответствующую первому числу из A.
  3. Удаляем v из N, удаляем первое число из A.
  4. Если в A осталось два числа — соединяем ребром соответствующие вершины, иначе — п. 1.