Дерево

в теории графов - связный неориентированный граф G, не содержащий циклов. Д. Не имеет кратных ребер и петель. Являясь простейшими связными графами, Д. Служат хорошими моделями для рассмотрения различных вопросов теории графов. Любое Д. С пвершинами содержит п-1 ребер. Число различных Д., к-рые можно построить на пнумерованных вершинах, равно nn-2. Д. С одной выделенной вершиной наз. Корневым деревом. Перечисляющий ряд для числа Т n неизоморфных корневых Д. С пвершинами удовлетворяет функциональному уравнению Перечисляющий ряд для числа tn неизоморфных Д. С n вершинами можно представить с помощью перечисляющего ряда для корневых Д. Функциональные уравнения для Т(х)и t(x)позволяют вычислять значения Т п и tn для конкретных значений п(см., напр., [1]).

Доказано, что при где С=0,534948;.., a=2,95576. (см. [2]). Задачи перечисления Д. Определенного вида возникают, напр., в химии при изучении изомеров. Д. Можно достаточно просто кодировать наборами из нулей и единиц. Рассмотрим, напр., к.-л. Правильную (без пересечения ребер) укладку Д. Dна плоскости (см. Графа укладка). Начиная с к.-л. Вершины, будем двигаться по ребрам Д. D, сворачивая в каждой вершине на ближайшее справа ребро и поворачивая назад в концевых вершинах Д. Проходя по нек-рому ребру, записываем 0 при движении по ребру в первый раз и 1 при движении по ребру второй раз (в обратном направлении). Если m- число ребер Д. D, то через 2т шагов мы вернемся в исходную вершину, пройдя по каждому ребру дважды. Полученная при этом последовательность из 0 и 1 (код Д.) длины 2m позволяет однозначно восстанавливать не только само Д.

D, но и его укладку на плоскости. Произвольному Д. Соответствуют несколько кодов. Из этого способа кодирования вытекает оценка. Tn<Tn<4n. Д. Gс пвершинами однозначно восстанавливается (с точностью до изоморфизма) по набору всех его (п-1)-вершинных подграфов G-v, получаемых из Gудалением каждой из его вершин v. Любое Д. Однозначно определяется также расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами. Остовное дерево (остов) - это подграф данного графа, содержащий все его вершины и являющийся Д. Число остовных Д. Произвольного связного графа Gбез петель и кратных ребер можно вычислить следующим образом. Пусть М- матрица, полученная из матрицы смежности графа Gизменением знаков всех элементов на противоположный и заменой i-го элемента главной диагонали степенью вершины vi.

Тогда алгебраич. Дополнения всех элементов главной диагонали матрицы Мравны между собой и их общее значение есть число остовов графа G. Остовные Д. Используются, напр., для нахождения независимых циклов в электрич. Схеме. Важное значение для приложений имеет задача нахождения в связном графе, ребрам к-рого приписаны веса, остовного Д. С наименьшей суммой весов ребер. Такая задача возникает, напр., при проектировании коммуникационных сетей. Известен алгоритм для решения этой задачи о кратчайшем связывающем дереве (см. [3]). Д., растущим (или выходящим) из вершины u0, наз. Ориентированный граф, к-рый является (без учета ориентации) корневым Д. С корнем u0 и в к-ром для любой вершины u1 (единственная) цепь, соединяющая v0 с v1, является ориентированным путем из v0 в v1.

Такие Д. Используются, напр., для описания детерминированных функций, для представления информации в информационно-поисковых системах и т. Д. Обобщением понятия "Д." является понятие "леса". Лес - это граф без циклов (не обязательно связный). Лит.:[1] ХарариФ., Теория графов, пер. С англ., М., 1973 (лит.). [2] Otter R., "Ann. Math.", 1948, v. 49, № 3, p. 583-99. [3] Прим Р. К., "Кибернетический сборник", 1961. В. 2, с. 95 - 107. В. Б. Алексеев..