Деревья и лес в теории графов
Дерево — это связный ациклический граф .Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.
Лес — упорядоченное множество упорядоченных деревьев.
Ориентированное (направленное) дерево — ацикличный орграф ( ориентированный граф , не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями.
Содержимое разработки
Определение. Н–граф называется неориентированным деревом (или просто деревом) если он связен и не содержит циклов, а значит петель и кратных ребер. Дерево – это минимальный связный граф в том смысле, что при удалении хотя бы одного ребра он теряет связность. Наличие этих двух свойств (связность и отсутствие циклов) позволяет жестко связать число вершин и число ребер: в дереве с 
вершинами всегда 
ребер. Пример графа–дерева приведен на рисунке 3.13. В этом графе 8 вершин и 7 ребер. Ни одно ребро нельзя удалить из графа без того, чтобы он не потерял связность.
Вершина 
графа 
называется концевой или висячей, если 
В графе на рис. 3.13 концевыми являются вершины 
.
Неориентированный граф–дерево может быть превращен в ориентированный. Ориентация неориентированного дерева проводится следующим образом. В дереве выбирается вершина 
– так называемый корень дерева , и все ребра такого дерева с корнем ориентируются от этой вершины – корня. Для каждой выбранной вершины ориентация дерева единственна, все ребра ориентированы от корня. Если изменить направления всех ребер ориентированного дерева (к корню) получим ориентированный граф, который иногда называют сетью сборки.
В каждую вершину ориентированного дерева (за исключением корня) входит только одно ребро. Любое дерево можно ориентировать, выбрав в качестве корня любую его вершину.
Пусть – вершина дерева с корнем , 
– множество всех вершин, связанных с корнем цепями, проходящими через вершину . Это множество порождает подграф 
, который называется ветвью вершины в дереве с корнем . Например, ветвью вершины 
на рис. 3.13 является подграф 
, содержащий вершины 
и ребра 
.
Определение. Лес – несвязный н–граф без циклов. Связные компоненты леса являются деревьями. Любая часть леса также является лесом или деревом. В неориентированном дереве между любыми двумя вершинами существует цепь и притом только одна.
Рассмотрим пример использование графа–дерева для решения задачи поиска гамильтоновых путей на взвешенном по ребрам графе, приведенном на рис. 3.14. Веса можно рассматривать как некоторый эквивалент затрат, связанных с переходом по ребру из одной вершины в другую. Будем считать, что коммивояжер отправляется из вершины 
, с тем, чтобы посетить вершины 
и вновь вернуться в .
Для решения задачи удобно воспользоваться вспомогательным графом–деревом, который позволяет не только получить все гамильтоновы пути, но и отслеживать вес каждого пути. Методика построения следующая: выделяется исходная вершина и ей присваивается нулевой вес. На вспомогательном графе такая вершина помечается как . Из исходной вершины проводятся ребра во все смежные вершины, по которым маршрут еще не проходил. Новым вершинам присваиваются веса, равный затратам, которые необходимо понести для их достижения из исходной вершины. Для рассматриваемого примера результатом первого шага станут вершины . Далее точно таким же образом производятся шаги из вновь полученных вершин, пока эти пути не приведут в исходную вершину. Часть путей могут быть тупиковыми, так как не позволяют завершить маршрут не заходя дважды в одну и ту же вершину. В данном примере, в частности, последовательность вершин является тупиковой.
Рис. 3.15. Граф–дерево, соответствующий полному перебору вариантов построения гамильтонового цикла в исходном графе рис. 3.14.
Приведенный на рис. 3.15 граф–дерево построен для решения задачи поиска кратчайшего гамильтонового пути с использованием метода полного перебора вариантов.
Проблема, однако, в том, что при большом числе вершин полный перебор вариантов, это работа, требующая огромных вычислений. В частности, для полного графа с вершинами число маршрутов равно . Если 5!=120, то 10!=3 628 800. И все-таки перебор маршрутов иногда бывает полезен. Известен метод решения задачи, в соответствии с которым шаг за шагом строится не полное, а «усеченное» дерево – часть ветвей в процессе его «выращивания» отсекаются, а оставшиеся ветви ведут к решению. Этот метод называется методом ветвей и границ.
Идея метода достаточно очевидна – каким-либо образом выбрать на графе некоторый путь, желательно покороче, а затем отбрасывать все варианты, которые явно длиннее. Простейшим алгоритмом может быть продолжение движения из вершины, имеющей минимальный вес. В рассмотренном примере, после первого шага, движение должно быть продолжено из вершины с наименьшим весом , что приводит в вершины и .
Выигрыш состоит в том, что неподходящие варианты просматриваются не до конца, а лишь до того момента, когда становится ясно, что рассматриваемый вариант хуже имеющегося. Общая полезность такого подхода зависит от степени дифференциации различных маршрутов, и от удачности построения первого маршрута. Ясно также, что в самом плохом случае мы получим полный перебор вариантов.
-82%
Источник
22. Классификация деревьев по Крафту.
Для лесоводов очень важно уметь правильно выделять деревья будущего и вести за ними уход, регулировать, а иногда заменять естественный отбор искусственным. В связи с этим необходимо определенным образом классифицировать деревья в лесу.
Одной из первых классификаций подобного рода была классификация немецкого лесовода Крафта, предложенная им в 1884 г. с целью ухода за лесом в чистых, одновозрастных древостоях.
Данная классификация наиболее удачная, ей пользуются и в настоящее время.
Согласно рассматриваемой классификации все деревья разбиваются на две большие группы – господствующие (по терминологии Крафта) и подчиненные.
Основными признаками для отнесения дерева к той или иной группе служат характер кроны и высота дерева. В пределах каждой из групп выделяют несколько классов.
І класс – исключительно господствующие деревья с мощно развитой кроной и крупными по высоте и диаметру стволами. В насаждении их около 10 % от общего количества, но они составляют до 20 % запаса.
ІІ класс – господствующие деревья с относительно хорошо развитыми кронами и почти такой же высотой, что и деревья І класса. В насаждении их 20-40 % от общего количества и около 40-60 % по запасу.
ІІІ класс – менее господствующие деревья, по высоте несколько уступают деревьям І и ІІ класса, кроны их менее развиты, сужены, нередко с признаками начинающегося угнетения. В насаждении их 20-30 % от общего количества и около 15-20 % по запасу.
Кроны деревьев І, ІІ и ІІІ классов создают основной, господствующий полог древостоя.
ІV класс – угнетенные деревья, кроны сжаты равномерно со всех сторон или односторонне, но вершины их входят в нижнюю часть основного полога.
По количеству деревьев их может быть до 30 %, но они создают не более 10 % запаса.
Деревья ІV класса делятся на два подкласса:
ІV а — имеют узкую, но равностороннюю крону,
ІV б – имеют одностороннюю, флагоподобную крону.
V класс – деревья, которые сильно отстали в росте, не достигают вершиной общего полога, отмирающие и мертвые.
Деревья V класса делятся на два подкласса:
V б – отмирают или усохли, но стоят на корнях.
Преимущества классификации Крафта:
1. отражает сущность дифференциации деревьев по росту в чистых одновозрастных насаждениях,
2. относительно проста и удобна в использовании,
3. помогает правильно назначать деревья в рубку при низовом методе.
Недостатки классификации Крафта:
1. субъективность и неоднозначность классов для разных биогрупп одного и того же древостоя,
2. ограниченность применения (только для чистых, одновозрастных, преимущественно хвойных древостоев),
3. затруднение в применении в высокопродуктивных сложных по форме древостоях.
23. Классификация деревьев по хозяйственно-биологическим признакам.
Классификация по хозяйственно-биологическим признакам, действующих «Правил рубок леса в лесах Республики Беларусь (2008).
Согласно данной классификации при проведении рубок ухода все деревья по хозяйственно-биологическим признакам распределяются на три категории:
ІІ категория – вспомогательные (полезные),
ІІІ категория – нежелательные (подлежащие рубке).
здоровые, имеющие прямые стволы, хорошо сформированные кроны, преимущественно семенного происхождения.
Они выбираются из деревьев главных пород І, ІІ и ІІІ классов роста.
Вспомогательные деревья:
способствуют очищению лучших деревьев от сучьев, формированию их стволов и крон, выполняют почвозащитные и почвоулучшающие функции.
Нежелательные (подлежащие рубке) деревья:
1. деревья разных пород, мешающие росту и формированию крон у лучших и вспомогательных деревьев;
2. кривые, с развилками и ответвлениями, многовершинные, сильно сбежистые;
3. сухостойные, буреломные, ветровальные, фаутныя и отмирающие.
Деревья, подлежащие рубке, могут быть всех классов роста и находиться во всех частях древостоев.
Источник
Наставление по рубкам ухода в лесах Урала (не применяется на основании приказа Рослесхоза от 14.11.2011 N 475)
3.1. Объектом ухода являются жизнеспособные и наиболее перспективные в росте деревья с нужными хозяйственными признаками. Такие деревья отбираются равномерно по площади. По отношению к ним оцениваются состояние, качество, положение в пологе и служебная роль других деревьев.
3.2. При проведении рубок ухода применяется лесоводственная (хозяйственно-биологическая) классификация, согласно которой все деревья по их биологическим и хозяйственным признакам подразделяются на три категории: I — лучшие (объект ухода), II — вспомогательные (способствующие росту лучших), III — нежелательные (мешающие росту лучших и подлежащие удалению).
3.3. К лучшим должны относиться здоровые деревья, имеющие прямой, полнодревесный, хорошо очищенный от сучьев ствол, равномерно развитую, неширокую, нормально охвоенную (облиственную), с нетолстыми сучьями крону, относительно быстрый рост, предпочтительно семенного происхождения. Лучшие деревья отбираются из деревьев главной породы I, II и III классов роста, как правило, из верхнего полога. Биологические особенности лучших деревьев должны соответствовать условиям местопроизрастания. К ним также могут относиться экземпляры кедра, ели, пихты и других ценных пород, способные после осветления быстро оправляться и увеличивать прирост. В сложных насаждениях лучшие деревья могут отбираться и из второго яруса.
Признаки лучших деревьев определяются в зависимости от целевого назначения лесов. В лесопарковых частях зеленых зон в качестве лучших могут отбираться деревья, имеющие причудливую форму ствола и кроны или другие особенности, представляющие декоративную ценность, а также деревья, сохраняющие лучшую жизнеспособность при уплотнении почвы или в условиях промышленных загрязнений. В лесах водоохранно-защитного назначения к лучшим следует относить деревья главных пород, отличающиеся долговечностью и формирующие ярусную корневую систему, в орехопромысловых зонах — рано, обильно и регулярно плодоносящие деревья кедра и т.д.
3.4. К вспомогательным относятся деревья, способствующие очищению лучших деревьев от сучьев, формированию стволов и крон, а также выполняющие почвозащитные и почвоулучшающие функции. Вспомогательные деревья могут быть всех пород и находиться в любой части полога, но преимущественно в подчиненной или образовывать второй ярус.
3.5. К нежелательным деревьям, подлежащим удалению, относятся:
а) мешающие росту и формированию крон лучших и вспомогательных деревьев (охлестывающие, затеняющие и т.д.) независимо от породы, высоты и диаметра;
б) сухостойные, буреломные, отмирающие, пораженные грибными заболеваниями и вредителями;
в) искривленные, с развилками или крупными пасынками, с сильно разросшейся, низко опущенной кроной и большим сбегом ствола, если эти деревья не играют полезной роли в насаждении и их вырубка не приведет к образованию больших просветов.
При большом количестве деревьев, указанных в подгруппе «в», удаление которых может вызвать недопустимое разреживание древостоя, часть их (с наименьшими дефектами) оставляется до следующей рубки. Деревья, подлежащие удалению, могут быть всех классов роста и находиться во всех частях полога.
3.6. Деревья, независимо от их категории, на которых расположены жилые гнезда птиц и логова зверей, а также располагающиеся в радиусе 1 м от муравейников, подлежат сохранению.
Источник