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

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

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

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

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

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

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

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

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

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

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

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

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

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

Будем преобразовывать последовательность 224466, действуя по следующей схеме. Вместо первого числа запишем наименьшее натуральное число, которое в этой последовательности не встречается, т.е. 1; получим последовательность 124466. Вместо второго числа в новой последовательности запишем наименьшее, не встречающееся в ней, т.е. 3; получим последовательность 134466, и т.д. Действуем так до тех пор, пока все числа в исходной последовательности не будут заменены. Расположим все последовательности друг под другом; под последней из них запишем код дерева. Выпишем пары вершин, записанные друг под другом в последних двух строчках: (12), (32), (24), (54), (46), (76). Каждая такая пара - это пара концов одного из ребер дерева. Этот список дополняем парой вершин, отсутствующих в предпоследней строчке, т.е. парой (6,8). Теперь строим дерево: отмечаем на плоскости точки – вершины дерева и соединяем их ребрами согласно списку (см. рисунок к примеру 3).

3.11. Остовы графа. Построение минимального остова

Напомним, что подграф графа , называется остовным подграфом, если .

Определение. Остовом обыкновенного графа называется его остовный подграф, являющийся деревом.

Пусть - обыкновенный граф. Упорядочим множество его вершин . Определим матрицу Кирхгофа графа , полагая:

где - матрица смежности графа, отвечающая данному упорядочению вершин.

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

Утверждение. Число остовов в связном неодноэлементном обыкновенном графе равно алгебраическому дополнению любого элемента его матрицы Кирхгофа.

Доказательство этого утверждения опустим.

Определение. Взвешенным графом будем называть совокупность объектов ,где тройка - граф и - отображение, называемое весовым.

Число называется весом ребра , число - весом графа .

Определение. Остов связноговзвешенного графа назовем минимальным остовом, если для любого остова выполнено неравенство .

Рассмотрим задачу о нахождении минимального остова в связном взвешенном графе.

Теорема (алгоритм Краскала). Пусть - связный взвешенный граф. - последовательность его остовных подграфов, заданная индуктивно следующим образом:

1. остовный подграф, множество ребер которого пусто.

2. Пусть - остовный подграф с множеством ребер . Тогда - остовный подграф с множеством ребер , где ребро выбирается из множества так, что выполнены два условия: а) добавление ребра не приводит к образованию циклов; б) из ребер, удовлетворяющих условию а), ребро обладает наименьшим весом.

Тогда последним элементом последовательности является минимальный остов графа .

Доказательство теоремы опустим.

Замечания. 1. Если граф несвязен, то по алгоритму Краскала строится остовный лес.

2. Если граф невзвешен, то, присваивая всем ребрам одинаковые веса, мы можем применить алгоритм Краскала для построения остова (остовного леса).

Пример 1. Построить остов минимального веса графа с множеством вершин ; множеством ребер ; отображением инцидентности , , , , , , , , и весовым отображением , , , , , , , .

Согласно алгоритму Краскала строим последовательность остовных подграфов:

с пустым множеством ребер;

с множеством ребер ;

с множеством ребер .

Добавление к графу любого из оставшихся ребер графа ведет к образованию цикла. Таким образом, подграф c множеством ребер , - минимальный остов, вес которого равен .