Дерево

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

Источник: Математическая энциклопедия на Gufo.me


Значения в других словарях

  1. дерево — -а, мн. деревья, -ьев и (устар.) дерева, -рев, ср. 1. Многолетнее растение с твердым стволом и ветвями, образующими крону. Хвойные деревья. Фруктовые деревья. □ На одном холме стояло дерево — очень высокая елка. М. Пришвин, Фацелия. Малый академический словарь
  2. дерево — Де́рев/о. Морфемно-орфографический словарь
  3. Дерево — I Де́рево долговечное растение (обычно не ниже 2 м) с многолетними деревенеющими стеблями и корнями. У Д., в отличие от кустарников, всегда выражен главный стебель — ствол с ветвями, образующими крону. Почти все... Большая советская энциклопедия
  4. дерево — орф. дерево, -а, мн. деревья, -ьев и (устар.) дерева, дерев и дерёв, деревам Орфографический словарь Лопатина
  5. дерево — Старославянское – древо. Слово «дерево» вошло в древнерусский язык в XI в., в отличие от старославянской формы, древнерусская характеризовалась полногласием. Слово имеет общую индоевропейскую основу deru-. Родственными являются: Литовское – derva (сосна). Этимологический словарь Семёнова
  6. Дерево — 1) благодаря удачному геогр. положению Палестины там растут почти все виды Д., обычно встречающиеся в областях с умеренным и жарким климатом; 2) в Лев 19:23-25 говорится о запрете есть плоды только что посаженного Д. в течение первых трех лет. (см. Библейская энциклопедия Брокгауза
  7. Дерево — Главные деревья в Палестине описываются в нашей Энциклопедии каждое под его собственным названием. Они сгруппированы вместе следующим образом писателем кн. Екклезиаст: я возвысился как кедр Ливанский и как кипарисовое дерево в горах Ермонских. Библейская энциклопедия архим. Никифора
  8. Дерево — Программирование Конечное множество, состоящее из одного или более узлов, удовлетворяющих следующим условиям.  — между узлами имеет место отношение типа исходный-порожденный;  — есть только один узел (корень), не имеющий исходного;  ... Словарь компьютерных терминов
  9. дерево — ДЕРЕВО — многолетнее растение (обычно не ниже 2 м) с одревесневшими стеблями и корнями. У Д. всегда выражен главный стебель — ствол с ветвями, образующими крону. Почти все деревья принадлежат к хвойным (из голосеменных) и двудольным (из покрытосеменных) растениям. Ботаника. Словарь терминов
  10. дерево — дерево (древо) балка, бревно, брус, валежник, буревал, бурелом, дрова, дром (дрюк), дручина, дручок, дубина, дылка, дыль, колода, кол, мачта, обрубок, оглобля, орясина, пень, плаха, полено, столб, тес, тычина, хворост, чурбан; головня, головешка собират. Словарь синонимов Абрамова
  11. дерево — сущ., с., употр. очень часто (нет) чего? дерева, чему? дереву, (вижу) что? дерево, чем? деревом, о чём? о дереве; мн. что? деревья, (нет) чего? деревьев, чему? деревьям, (вижу) что? деревья, чем? деревьями, о чём? о деревьях... Толковый словарь Дмитриева
  12. дерево — Общеслав. Суф. производное (ср. древеса) от той же основы, что и драть, др.-инд. dāru, греч. dory, хеттск. taru и т. д. Первоначальное значение сущ. дерево — «выдранное или ободранное» (ср. диал. деревки «росчисть, подсека», т. е. расчищенное от деревьев место). Этимологический словарь Шанского
  13. ДЕРЕВО — ДЕРЕВО, крупное многолетнее растение с одним сильно развитым одревесневшим главным стеблем (стволом) и более мелкими ветвями. Ствол ежегодно увеличивается в диаметре; листья могут быть либо ВЕЧНОЗЕЛЕНЫМИ, либо ОПАДАЮЩИМИ. Научно-технический словарь
  14. дерево — (arbor), растение с многолетним, в разл. степени одревесневающим, разветвлённым или неветвяшимся главным стеблем — стволом, сохраняющимся в течение всей жизни растения, и кроной. Биологический энциклопедический словарь
  15. дерево — Растение, для которого характерно наличие многолетнего, как правило, одиночного ствола и кроны. При торможении развития главного побега усиливается его ветвление, нередко приводящее к возникновению многоствольной формы. Биология. Современная энциклопедия
  16. дерево — ДЕРЕВО -а; мн. деревья, -вьев и (устар.) дерева, -рев; ср. 1. Многолетнее растение с твёрдым стволом и ветвями, образующими крону. Хвойные деревья. Фруктовые деревья. Высокое раскидистое старое д. Больное, засохшее д. Посадить, вырастить... Толковый словарь Кузнецова
  17. дерево — ДЕРЕВО, а, мн. деревья, ьев (устар. высок. дерева, дерев, деревам), ср. 1. Многолетнее растение с твёрдым стволом и отходящими от него ветвями, образующими крону. Хвойные, лиственные деревья. 2. ед. То же, что древесина (во 2 знач.). Толковый словарь Ожегова
  18. дерево — ДЕРЕВО или древо; мн. дерева, деревья, древа, древеса ср. самое крупное и рослое растение, которое выгоняет от корня один пень или лесину и состоит из древесины, древесных волокон, придающнх ему плотность и крепость. Толковый словарь Даля
  19. дерево — Д’ЕРЕВО, дерева, мн. деревья, деревьев, и (·устар. ·обл. и спец.) дерева, дерёв, ср. 1. Многолетнее растение с твердым стволом и ветвями, образующими крону. 2. Бревно, брус (·обл., спец.). На сарай пошло тридцать дерёв. 3. только ед. Толковый словарь Ушакова
  20. дерево — Общеславянское слово, имеющее соответствия в других языках. Общеславянское слово имеет вид dervo и образовано от основы der (с той же основой, но измененной гласной мы имеем дело в глаголе драть). Этимологический словарь Крылова
  21. дерево — дерево I ср. 1. Многолетнее растение с твёрдым стволом и отходящими от него ветвями, образующими крону. 2. Бревно, брус. 3. Древесина, древесный материал, идущий на постройки и изделия. 4. разг. Изделия из такого древесного материала. II ср. разг. Толковый словарь Ефремовой
  22. ДЕРЕВО — ДЕРЕВО — многолетнее растение с одревесневшим главным стеблем (стволом) — сохраняющимся в течение всей его жизни, и ветвями, образующими крону. Высота от 2 до 100 м, изредка больше. Отдельные виды (напр., сосна остистая) живут до 3-5 тыс. лет. Большой энциклопедический словарь
  23. дерево — де́рево мн. дере́вья (из собир. *dervьje, диал. дерева́), укр. де́рево, ст.-слав. дрѣво, род. п. дрѣвесе и дрѣва ξύλον, δένδρον (Мейе 360), сербохорв. дри̏jево, словен. drevô, drevė̑sa, чеш. dřevo, слвц. drevo, польск. drzewo, в.-луж. drjewo, н.-луж. Этимологический словарь Макса Фасмера