ДЕРЕВО

ДЕРЕВО

в теории графов - связный неориентированный граф 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.

В. Б. Алексеев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем решить контрольную работу
Синонимы:
, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,


Полезное


Смотреть что такое "ДЕРЕВО" в других словарях:

  • дерево — Балка, бревно, брус, валежник, буревал, бурелом, дрова, дром (дрюк), дручина, дручок, дубина, дылка, дыль, колода, кол, мачта, обрубок, оглобля, орясина, пень, плаха, полено, столб, тес, тычина, хворост, чурбан; головня, головешка. Собират.:… …   Словарь синонимов

  • ДЕРЕВО — или древо; мн. дерева, деревья, древа, древеса ср. самое крупное и рослое растение, которое выгоняет от корня один пень или лесину и состоит из древесины, древесных волокон, придающнх ему плотность и крепость. Меньшие деревья, не достигаюшие… …   Толковый словарь Даля

  • ДЕРЕВО — (arbor), растение с многолетним, в разл. степени одревесневающим, разветвлённым или неветвяшимся главным стеблем стволом, сохраняющимся в течение всей жизни растения, и кроной. Типичная крона из ветвей образуется у хвойных (из голосеменных) и… …   Биологический энциклопедический словарь

  • ДЕРЕВО — фундаментальный культурный символ, репрезентирующий вертикальную модель мира, семантически фундированную идеей бинарных оппозиций (как космологически, так и аксиологически артикулированных). В традиционной культуре выступает основополагающим… …   История Философии: Энциклопедия

  • дерево — ДЕРЕВО, а, ср и в зн. сказ. (или здравствуй, дерево, полное дерево, африканское дерево). Глупый человек, тупица, бездарь. Он полное дерево, он таблицу умножения с законами октябрят путает. См. также пробковое дерево …   Словарь русского арго

  • ДЕРЕВО — ДЕРЕВО, крупное многолетнее растение с одним сильно развитым одревесневшим главным стеблем (стволом) и более мелкими ветвями. Ствол ежегодно увеличивается в диаметре; листья могут быть либо ВЕЧНОЗЕЛЕНЫМИ, либо ОПАДАЮЩИМИ. Самое большое из… …   Научно-технический энциклопедический словарь

  • Дерево — [tree] в теории графов, связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин  (элементов графа), то он содержит ровно n 1 ребро, не имеет циклов; если добавить… …   Экономико-математический словарь

  • ДЕРЕВО — ДЕРЕВО, дерева, мн. деревья, деревьев, и (устар. обл. и спец.) дерева, дерёв, ср. 1. Многолетнее растение с твердым стволом и ветвями, образующими крону. 2. Бревно, брус (обл., спец.). На сарай пошло тридцать дерёв. 3. только ед. Древесина,… …   Толковый словарь Ушакова

  • ДЕРЕВО — ДЕРЕВО, а, мн. деревья, ьев (устар. высок. дерева, дерев, деревам), ср. 1. Многолетнее растение с твёрдым стволом и отходящими от него ветвями, образующими крону. Хвойные, лиственные деревья. 2. ед. То же, что древесина (во 2 знач.). Мебель… …   Толковый словарь Ожегова

  • дерево... — ДЕРЕВО... Первая часть сложных слов. Вносит зн. сл.: дерево. Деревопереработка, дереворежущий …   Энциклопедический словарь

  • ДЕРЕВО — многолетнее растение с одревесневшим главным стеблем (стволом), сохраняющимся в течение всей его жизни, и ветвями, образующими крону. Высота от 2 до 100 м, изредка больше. Отдельные виды (напр., сосна остистая) живут до 3 5 тыс. лет. Деревья… …   Большой Энциклопедический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»