Дерево - это специфический вид графов. Деревом называется связный граф, не содержащий циклов. Любой граф, не содержащий циклов, называется ациклическим, или лесом. Компонентами леса являются деревья.
Пример:
 |
ДРУГИЕ ОПРЕДЕЛЕНИЯ ДЕРЕВА
Теорема, дающая 5 различных определений дерева (теорема эквивалентности).
Для любого (p,q) - графа следующие утверждения эквивалентны:
1) граф G – дерево: связный ацикличный граф;
2) любые две несовпадающие вершины графа G соединены единственной простой цепью;
3) граф G связен и q=p-1(количество ребер в нем на 1 меньше, чем количество вершин);
4) граф G ацикличен и q=p-1;
5) граф G ацикличен и, если любую пару его несовпадающих несмежных вершин соединить ребром е, то полученный граф G+e будет содержать в точности один цикл.
Теорема о висячих вершинах дерева.
В любом нетривиальном (
) дереве имеются, по крайней мере, две висячие вершины.
Теорема о центральных вершинах дерева.
Центр любого дерева состоит либо из одной, либо из двух (смежных) вершин.
ЯРУСНАЯ ФОРМА ПРЕДСТАВЛЕНИЯ ДЕРЕВЬЕВ
 |
Выберем некоторую произвольную фиксированную вершину дерева и назовем ее корнем. Будем полагать, что корень дерева расположен на 0 ярусе. Все остальные вершины сориентируем относительно корня следующим образом: на i-й ярус поместим вершины с расстоянием от корня, равным i. Концевые висячие вершины будем называть листами, а геодезические от корня к листу - ветвями.
СПОСОБЫ ОБХОДА ДЕРЕВЬЕВ
Существует два основных способа.
1. 
Способ обхода (поиска) в глубину подразумевает просмотр ветвей в ярусном представлении дерева.
Начинаем поиск с некоторой фиксированной вершины v0. Находим вершину u, смежную с v0, и повторяем процесс, начиная с вершины u:
- если существует не просмотренная вершина, смежная с вершиной u, рассматриваем ее и, начиная с нее, продолжаем поиск;
- если не существует ни одной новой вершины, смежной с u, то говорят, что вершина u использована, и делается возврат в вершину, из которой мы попали в вершину u; продолжаем процесс;
- если на каком-то шаге u= v0, и нет ни одной не просмотренной вершины, смежной v0, то алгоритм заканчивает работу.
2. Способ обхода (поиска) в ширину подразумевает просмотр вершин по ярусам с перебором вершин одного яруса.
 |
ОСТОВЫ
Остов (каркас, скелет) графаG – это остовный подграф графа G, задающий дерево на каждой компоненте связности графа G.
Для связного графа остов – это дерево, покрывающее все вершины исходного графа.
Пусть есть некоторый граф G:
Очевидно, что в каждом графе существует остов, в общем случае, не один. Его можно получить, разрушая циклы в каждой компоненте связности.
Ребра остова Т некоторого графа G называются ветвями, а ребра графа G, не вошедшие в остов, называются хордами.
В первом остове графа G: (v2,v3 ), (v3,v4 ), (v4,v5 ), (v5,v6 ), (v1,v6 ) -ветви;
(v1,v2 ), (v2,v6 ), (v2,v5 ), (v3,v6 ), (v3,v5 ) -хорды.