Skip to content

Even Tree

Even Tree — это алгоритм, решающий задачу о максимальном удалении рёбер из дерева так, чтобы в каждой оставшейся компоненте связности было чётное число вершин. Этот метод применяется в задачах, где требуется разбить структуру на сбалансированные поддеревья, например, для распределения ресурсов, кластеризации данных или оптимизации сетей.

Основные бласти применения

  1. Сетевые технологии (разбиение графов на поддеревья с чётным числом узлов в телекоммуникациях)
  2. Компьютерные науки (балансировка нагрузки между серверами с чётным числом подключений)
  3. Социальные сети (анализ сообществ с чёткими парными связями, например, разбиение на пары для совместных проектов)
  4. Биотехнологии и медицина (моделирование молекулярных структур с чётными связями)
  5. Логистика (оптимальное разделение маршрутов доставки на чётные кластеры для сбалансированного распределения)

Формулировка задачи

Дано:

  • Дерево (связный ациклический граф) из N вершин (где N чётно).

Необходимо:

  • Удалить максимальное количество рёбер так, чтобы в каждом получившемся поддереве было чётное число вершин.

Пример:

      1
    / | \
   2  3  4
     / \
    5   6

Здесь можно удалить рёбра (1, 3) и (3, 5), получив три поддерева с чётным числом вершин: [1, 2, 4], [3, 6], [5] (но [5] нечётное → ошибка). Правильное решение — удалить только (1, 3), получив [1, 2, 4] и [3, 5, 6] (оба чётные).

Реализация на Python

from collections import defaultdict

def even_tree(graph, n):
    visited = [False] * (n + 1)
    count = [0] * (n + 1)
    removable_edges = 0

    def dfs(node):
        nonlocal removable_edges
        visited[node] = True
        count[node] = 1  # учитываем саму вершину

        for neighbor in graph[node]:
            if not visited[neighbor]:
                count[node] += dfs(neighbor)

        # Если количество вершин в поддереве чётное, можно удалить ребро
        if count[node] % 2 == 0 and node != 1:
            removable_edges += 1
            count[node] = 0  # "отрезаем" поддерево

        return count[node]

    dfs(1)  # Запускаем обход из корня (1)
    return removable_edges

# Пример использования
if __name__ == "__main__":
    # Дерево: 1 - {2, 3, 4}, 3 - {5, 6}
    edges = [(1, 2), (1, 3), (1, 4), (3, 5), (3, 6)]
    n = 6  # Число вершин

    # Строим граф в виде списка смежности
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    print("Максимальное число удаляемых рёбер:", even_tree(graph, n))