Понятие - дерево
Cтраница 1
Понятие дерева как математического объекта было впервые предложено Кирхгофом [36] в связи с определением фундаментальных циклов, применяемых при анализе электрических цепей. Приблизительно десятью годами позже Кэли [5] вновь ( независимо от Кирхгофа) ввел понятие дерева и получил большую часть первых результатов в области исследования свойств деревьев. [1]
Понятие дерева отказов ( fault tree) возникло в связи с анализом надежности сложных систем. Целью построения такого дерева отказов является символическое представление последовательности возникновения условий, приводящих систему к отказу, нежелательному ( критическому) для объекта в целом. [2]
Понятие дерева подчинения формализует обычные школьные представления о синтаксич. [3]
Обобщение понятия дерева до графа аналогично переходу от древовидного к сетевому представлению данных. При векторном виде данных в древовидном представлении склейка данных может быть сделана только по начальному отрезку; в сетевом представлении она допустима по любым отрезкам. В сетевой модели данных доступ к данным может быть осуществлен по многим путям. Она позволяет реализовать более широкий класс отношений между объектами, чем древовидная. Поскольку сетевая модель является обобщением древовидной, то она предоставляет больше возможностей как для описания предметной области, представляемой БД, так и для нахождения оптимальных решений хранения и поиска данных. Но использование сетевой модели требует высокой квалификации от разработчика и поэтому она не была воспринята массовым пользователем. [4]
С понятием дерева связаны понятия главных контуров и главных сечений. [5]
 |
Дерево двоичного поиска. [6] |
Хотя наше определение понятия дерева требует, чтобы дерево содержало хотя бы один узел, а именно корень, во многих алгоритмах мы будем трактовать пустое дерево ( дерево без узлов) как двоичное. [7]
Кэли также увидел, что понятие дерева можно использовать при изучении проблемы изомеров в химии, но для этого необходимо учитывать ограничения на степени вершин. В 1931 г. Хенце и Блейр [2] получили рекуррентные формулы для подсчета числа конечных деревьев, у которых степени вершин не превышают четырех, а также конечных корневых деревьев, у которых степень корня не больше трех, а степени остальных вершин не превосходят четырех. [8]
С выполнимостью элементарного совета связано понятие форсированного дерева. Форсированное дерево задает детальную стратегию, которая гарантирует достижение главной цели при выполнении всех ограничений, содержащихся в элементарном совете. Таким образом, форсированное дерево указывает, как именно должен ходить игрок при любых ответах противника. [9]
В этой главе будет введено понятие потоково-эквивалентного дерева, которое нам пригодится в дальнейшем. [10]
Обратим внимание читателя на дополнительность понятий покрывающего дерева и разреза. Первое понятие характеризует минимальное множество ребер, которое связывает все вершины графа, а второе - минимальное множество ребер, отделяющее некоторые вершины графа от остальных. Объединяя сделанные замечания и определения, получаем следующий результат. [11]
Рабин [1972] предложил одно интересное обобщение понятия дерева решений. [12]
Возьмем, говорит один из психологов, пример - понятие дерева. Оно получается из ряда сходных представлений дерева. Понятие возникает из представлений единичных сходных предметов. Далее идет схема, которая поясняет процесс образования понятия и которая представляет его в следующем виде. Положим, я имел случай наблюдать три различных дерева. Представления этих трех деревьев могут быть разложены на свои составные части, из которых каждая обозначает форму, цвет или величин отдельных деревьев. Остальные составные части этих представлений оказываются сходными. [13]
Для описания взаимосвязи между Л - и В вводят понятие дерева. Дерево есть связанный ( связь существует между любыми двумя вершинами) подграф связанного графа, включающий все вершины графа и не содержащий замкнутых контуров. [14]
Не все методы могут быть адекватно описаны на основе раздельных понятий дерева поиска и дерева доказательства. Некоторые методы конструируют несколько иные виды деревьев. Например, метод резолюции, который описан в следующем разделе, конструирует единственный тип дерева, объединяющий черты деревьев поиска и доказательства. [15]
Страницы: 1 2 3