Cтраница 2
В цепи, содержащей п узлов, дерево имеет - 1 ветвей, соединяет все узловые пары и не образует контуров. Любые два из этих трех свойств могут быть использованы для определения дерева, а третье свойство вытекает из двух других. Для удобства и простоты будем применять термин дерево также вместо величина дерева, так как различие между этими терминами будет очевидно из текста. [16]
В параграфе 1.6 этот подход применяется к изучению максимального размера дерева в случайном лесе из некорневых деревьев. Теоремы 1.6.1 - 1.6.5 полностью описывают поведение этого максимума при всех возможных случаях регулярного изменения параметров п и ЛГ, за исключением случая фиксированного N. Ясно, что для любого фиксированного k размер k - то по величине дерева в случайном лесе может быть также изучен с помощью использованного подхода. Эта возможность была реализована Лучаком и Питтелем в [156], результаты этой статьи интерпретируются как эволюция случайного леса, при этом отмечается возникновение так называемой гигантской компоненты - дерева в конце процесса эволюции. [17]
Связный неориентированный граф, не содержащий циклов, называется деревом. В частности, дерево не имеет петель и кратных ребер. Любая цепь в графе без циклов является простой; любая часть такого графа также будет графом без циклов. В дереве любые две вершины связаны единственной цепью. Величина дерева равна произведению величины его ребер. [18]
Любая из вершин графа может быть условно принята за начальную, и ее называют базой, или корне м, дерева графа. Базовым ( корневым) деревом является цепь, проходящая через вершины дерева к базе и в ней заканчивающаяся. Таким образом, ориентированный граф может быть охарактеризован определенной системой уравнений. При этом величина маршрута графа выражается произведением величин ребер, причем величины кратных ребер ( в данном направлении) складываются. Аналогичным образом, величиной дерева является произведение величин всех составляющих его ребер. [19]