Какие условия делают граф деревом?

В теории графов дерево — это связный ациклический граф. Для графа (G = (V, E)) (где (V) — вершины, (E) — рёбра) следующие условия эквивалентны и определяют дерево:

1. Связность: Между любыми двумя вершинами существует ровно один простой путь.
2. Отсутствие циклов: Граф не содержит циклов.
3. Соотношение рёбер и вершин: Граф с (n) вершинами имеет ровно (n-1) ребро.

Почему это важно в программировании? Деревья — фундаментальная структура данных (бинарные деревья, AST, DOM, графы зависимостей).

Пример проверки (псевдокод):

# Функция проверки, является ли граф деревом
def is_tree(graph):
    n = len(graph.vertices)
    # Условие 1: количество рёбер = n - 1
    if len(graph.edges) != n - 1:
        return False
    # Условие 2: граф связный (проверяется, например, обходом в глубину - DFS)
    visited = dfs_traversal(graph, start_vertex=0)
    if len(visited) != n:
        return False
    # Если оба условия выполнены и DFS не обнаружил циклов -> это дерево
    return True

Ключевые свойства деревьев:

• Добавление любого нового ребра создаст цикл.
• Удаление любого ребра разобьёт дерево на две компоненты связности.