- Граф называется деревом, если он связный и не имеет циклов.
- Отличительной особенностью дерева является то, что между любыми двумя его вершинами существует единственный путь.
- Свойства дерева:
- нет замкнутых цепей;
- любые две вершины соединены единственной ветвью;
справедливо следующее соотношение:
где
p – число вершин, q – число рёбер;- если любые две вершины в дереве соединить ребром, то получится только одна замкнутая цепь.
