ДЕРЕВО

в теории графов - связный неориентированный граф 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, но и его укладку на плоскости. Произвольному Д. соответствуют несколько кодов. Из этого способа кодирования вытекает оценка: tnn<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.

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


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



Математическая энциклопедия 

ДЕСКРИПТИВНАЯ ТЕОРИЯ МНОЖЕСТВ →← ДЕНУМЕРАНТ

T: 0.207203794 M: 3 D: 3