1. Деревом называется связный ациклический граф, в котором между любыми двумя вершинами существует ровно один путь.
2. Свойства деревьев:
- Дерево с n вершинами содержит n - 1 рёбер.
- Между любыми двумя вершинами дерева существует единственный путь.
- Удаление любого ребра из дерева делает его несвязанным (разделяет на две компоненты).
- В любом дереве есть по крайней мере одна степень вершины, равная 1 (лист).
- Любое дерево можно рассматривать как минимальное связное подмножество графа.