Понятие - дерево
Cтраница 2
Целью настоящей главы является изучение циклов в графах и исследование некоторых из их свойств и связей с другими понятиями ( такими, как понятие дерева), введенными ранее. Два тип циклов в графах, эйлеровы и гамильтоновы циклы, часто встречаются в практических задачах и поэтому представляют особый интерес. Первые из них рассмотрены в настоящей главе, а вторые - в следующей. [16]
Целью настоящей главы является изучение циклов в графа и исследование некоторых из их свойств и связей с другими понятиями ( такими, как понятие дерева), введенными ранее. Два тип циклов в графах эйлеровы и гамильтоновы циклы, часто встречаются в практических задачах и поэтому представляют особый интерес. Первые из них рассмотрены в настоящей главе, а вторые - в следующей. [17]
Для выбора контура таким образом, чтобы в каждый из них входило по одной ветви, не входящей в остальные контуры, используют понятие дерева. Под деревом понимают совокупность ветвей, касающихся всех узлов, но не образующих ни одного за м кнутого контура. [18]
Если в табличном представлении произвести лексикографическое упорядочение и сделать склейку по совпадающим префиксам, то получается древовидное представление данных, в основе которого лежит понятие дерева. Такое представление ведет к большей компактности данных и к ускорению поиска нужных данных. Такие древовидные структуры, как бинарные деревья, 2 - 3-деревья, В-деревья, сортирующие деревья [10] используются для внутреннего представления данных. Древовидное представление удобно использовать в лингвистических и подобных им БД, например, когда надо найти то или иное слово. Древовидное представление все еще достаточно просто для понимания, хотя и не так наглядно как табличное. [19]
Кнутом в [48], они позволяют использовать до 2 / 3 имеющегося в каждой вершине пространства. Плотные то-арные деревья основаны на понятии братского дерева и позволяют строить деревья с наперед заданной плотностью заполнения вершин. Этот тип деревьев был предложен в 1979 г. К. [20]
I мы кратко исполыовали деревья при изучении необходимого числа взвешиваний в задаче о фальшивой монете с п монетами. Так рано деревья появились не случайно, ибо понятие дерева используется в различных важных аспектах в каждой главе книги. [21]
Но мы рассматриваем их в одном параграфе ввиду родства понятий дерева и прадерева. [22]
Тот факт, что любой связный граф содержит в качестве своего связного подграфа дерево, использовался, например, в работе [16] при построении по данному графу связных графов с большим цикломатическим числом и в работах [17] - [19] для оценки сверху скорости убывания многоточечных корреляций. В [20] строится классификация связных непомеченных графов, в которой понятие дерева используется для формулировки алгоритма построения более сложных графов из данных графов. При этом, однако, расссматривамое дерево не является каким-либо подграфом строящихся графов. [23]
Между сходными частями этих предстаатений должна произойти ассимиляция, результатом чего явится общее представление данного признака. Затем благодаря синтезу этих представлений получается одно общее представление, или понятие дерева. [24]
В главе 7 будет показано, что свойства разрезов тесно связаны с максимальным потоком в соответствующей сети. Определение основных матриц для циклов и разрезов в существенной мере основывается на понятиях дерева, ветвей дерева и хорд. [25]
Понятие дерева как математического объекта было впервые предложено Кирхгофом [36] в связи с определением фундаментальных циклов, применяемых при анализе электрических цепей. Приблизительно десятью годами позже Кэли [5] вновь ( независимо от Кирхгофа) ввел понятие дерева и получил большую часть первых результатов в области исследования свойств деревьев. [26]
Граф называется деревом, если он связен и не имеет циклов. Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Понятие дерева играет важную роль во многих разделах теории графов. Граф является деревом тогда и только тогда, когда каждая пара различных вершин соединяется одной и только одной цепью. Связность означает существование, по крайней мере, одной цепи, а из отсутствия циклов следует существование единственной такой цепи. [27]
Корневое дерево на рис. 2.3 содержит 9 узлов, помеченных буквами от а до г. Узлы с метками e f, ct g, h, r являются листьями, остальные узлы - внутренние. Понятие дерева используется в различных аспектах. Деревья - наиболее важные нелинейные объекты, используемые для представления данных в алгоритмах на дискретных структурах. [28]
 |
Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [29] |
Ребра дерева называют ветвями, а ребра, образующие дополнение дерева, - хордами. Связный граф с v вершинами и е ребрами содержит v - 1 ветвей и е - v 1 хорд. С использованием понятия дерева связано определение числа независимых уравнений Кирхгофа, метода выбора независимых уравнений, структуры коэффициентов матриц уравнений и формулы функций цепей. [30]
Страницы: 1 2 3