2.4. Деревья в теории графов

Представьте себе организационную схему крупной компании. В самом верху будет руководитель, чуть ниже — его заместители, затем — главы департаментов и подчинённые им главы отделов. В самом низу — линейные сотрудники.

В мире графов такие схемы называются деревьями. Они выделяются своей уникальной структурой: деревья не содержат циклов, всегда связны и имеют ровно на одно ребро меньше, чем вершин.

Эти свойства делают деревья чрезвычайно удобными для задач, где важно избежать избыточности и построить оптимальные связи. Именно поэтому деревья заслуживают отдельного внимания как одна из ключевых моделей в теории графов.

Типы деревьев

Остовное дерево — это подграф связного графа, который содержит все его вершины и также представляет собой дерево.

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

Если мы возьмём несколько деревьев и поместим их вместе без соединения между ними, мы получим лес.

В терминологии графов это несвязный неориентированный граф без циклов, состоящий из нескольких компонент, каждая из которых является деревом. Как множество отдельных островов с собственными деревьями, не связанных между собой.

С типами разобрались, давайте теперь рассмотрим ключевые теоремы о деревьях.

Теоремы о деревьях

Деревья обладают рядом уникальных свойств, которые делают их удобными для анализа и практических задач:

1. У дерева всегда есть хотя бы одна висячая вершина.
2. В дереве число вершин всегда на единицу больше, чем число рёбер.
3. У любого связного графа существует остовное дерево

Это важно: свойство №1 лежит в основе многих алгоритмов обработки деревьев. Свойство №2 помогает интуитивно понять структуру деревьев. А свойство №3 помогает оптимизировать графы.

И вот как можно формализовать и доказать эти свойства.

Теорема №1: висячая вершина в дереве

У нас есть утверждение, что в дереве с более чем одной вершиной всегда есть хотя бы одна висячая вершина.

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

Теорема №2: соотношение между вершинами и рёбрами

Утверждение следующее: в дереве число вершин на единицу больше, чем число рёбер, то есть , где — число вершин, — число рёбер.

Доказательство по индукции:

• База индукции: Для дерева с одной вершиной нет рёбер и соотношение выполняется.
• Шаг индукции: Предположим, что теорема верна для всех деревьев с вершиной. Возьмём дерево с вершинами. По теореме 1, у него есть висячая вершина. Удалим эту вершину и её единственное ребро. Оставшееся — дерево с вершиной и рёбрами, для которого, по предположению, верно . Возвращаясь к исходному дереву, получаем .

Это как строить цепочку из звеньев: каждое новое звено (вершина) добавляет одну связь (ребро), сохраняя целостность цепочки без замкнутых колец.

Теорема №3: остовное дерево связного графа

Мы утверждаем, у любого связного графа существует остовное дерево.

Рассмотрим связный граф, который можно представить как структуру со множеством узлов и циклов. Наша задача — удалить из графа избыточные рёбра, сохраняя связность и избегая образования циклов.

1. Начинаем с исходного связного графа.
2. Пока присутствуют циклы, удаляем по одному ребру из каждого из них. Это сохраняет связность, но устраняет замкнутость.
3. В результате получаем граф без циклов, который остаётся связным, — остовное дерево.

Мы рассмотрели основные свойства и теоремы, которые формализуют фундаментальные характеристики деревьев, подчёркивая их простоту и эффективность. Однако на практике связи между объектами редко бывают равнозначными: они часто сопровождаются дополнительной информацией — некоторыми весами.

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

Взвешенные деревья

В реальном мире связи между объектами часто имеют вес: расстояние между городами, стоимость перелётов, время передачи данных. Взвешенное дерево учитывает эти веса, что позволяет решать задачи оптимизации. Вес ребра может представлять различные величины, например:

• Расстояние. В транспортной сети вес ребра может представлять расстояние между двумя городами.
• Время. В сети передачи данных вес ребра может представлять время, необходимое для передачи данных между двумя узлами.
• Стоимость. В сети поставок вес ребра может представлять стоимость перевозки груза между двумя складами

Для поиска оптимальных путей во взвешенных деревьях есть специальные алгоритмы. Рассмотрим их подробнее.

Алгоритм Дейкстры

Суть:

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

Принцип работы:

Представьте, что вы путешественник в незнакомом городе и хотите посетить все достопримечательности с минимальными затратами времени.

1. Инициализация:
   • Устанавливаем начальную вершину с нулевым расстоянием.
   • Остальные вершины получают бесконечное расстояние.
   • Все вершины считаются необработанными.
2. Шаги алгоритма:
   • Выбираем необработанную вершину с наименьшим текущим расстоянием до неё.
   • Для каждого соседа текущей вершины:
     • Вес ребра между текущей вершиной и соседом — это заданная величина, характеризующая связь между ними.
     • Вычисляем новое потенциальное расстояние до соседа: сумма текущего расстояния до вершины и веса ребра между ними.
     • Если это расстояние меньше ранее известного расстояния до соседа, обновляем его.
   • Помечаем текущую вершину как обработанную.
3. Завершение:
   • Процесс повторяется, пока все вершины не будут обработаны.

Преимущества и ограничения:

• Плюсы: эффективен и гарантирует оптимальные решения для графов с неотрицательными весами.
• Минусы: не работает с отрицательными весами рёбер.

import heapq

def dijkstra(graph, start):
    distance = {vertex: float('inf') for vertex in graph}
    distance[start] = 0
    priority_queue = [(0, start)]  # (расстояние, вершина)

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # Если найден более короткий путь, пропускаем
        if current_distance > distance[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance_to_neighbor = current_distance + weight

            if distance_to_neighbor < distance[neighbor]:
                distance[neighbor] = distance_to_neighbor
                heapq.heappush(priority_queue, (distance_to_neighbor, neighbor))

    return distance

# Пример использования
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

distances = dijkstra(graph, 'A')
print(distances)  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Алгоритм Беллмана — Форда

Суть:

Позволяет находить кратчайшие пути от заданной вершины до всех остальных, даже если в графе присутствуют отрицательные веса рёбер. Однако алгоритм лучше применять для средних по размеру графов, поскольку его временная сложность составляет , где:

• — количество вершин в графе,
• — количество рёбер в графе.

Принцип работы:

Алгоритм последовательно релаксирует (обновляет) расстояния, проходя по всем рёбрам многократно.

1. Инициализация:
   • Как в алгоритме Дейкстры.
2. Шаги алгоритма:
   • Повторяем процесс релаксации ребер раз, где — количество вершин.
   • Проверяем на наличие отрицательных циклов.

Преимущества и ограничения:

• Плюсы: работает с отрицательными весами.
• Минусы: более медленный, сложность .

def bellman_ford(graph, source):
    distance = {vertex: float('inf') for vertex in graph}
    distance[source] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex]:
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    # Проверка на отрицательные циклы
    for vertex in graph:
        for neighbor, weight in graph[vertex]:
            if distance[vertex] + weight < distance[neighbor]:
                raise ValueError("Граф содержит отрицательный цикл")

    return distance

# Пример использования
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', -1), ('D', 2)],
    'C': [('D', 3)],
    'D': []
}

distances = bellman_ford(graph, 'A')
print(distances)  # {'A': 0, 'B': 4, 'C': 2, 'D': 5}

Алгоритм Флойда — Уоршелла

Суть:

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

При этом алгоритм способен обрабатывать графы с отрицательными весами рёбер, хотя его сложность делает его менее эффективным для очень больших сетей.

Принцип работы:

Представьте, что вы хотите узнать минимальные расстояния между всеми парами городов в стране.

1. Инициализация:
   • Создаём матрицу расстояний между всеми вершинами.
2. Шаги алгоритма:
   • Постепенно улучшаем оценки расстояний, рассматривая все возможные промежуточные вершины.

Преимущества и ограничения:

• Плюсы: работает с отрицательными весами рёбер и прост в реализации.
• Минусы: сложность делает алгоритм медленным для больших графов.

import numpy as np

def floyd_warshall(graph):
    num_vertices = len(graph)
    dist = np.array(graph)

    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# Пример использования
graph = [
    [0, 3, float('inf'), 5],
    [2, 0, float('inf'), 4],
    [float('inf'), 1, 0, float('inf')],
    [float('inf'), float('inf'), 2, 0]
]

shortest_paths = floyd_warshall(graph)
print(shortest_paths)

Теория графов и, в частности, деревья — это мощный инструмент для моделирования и решения разнообразных задач. Понимая, как элементы связаны между собой, мы можем принимать более обоснованные решения и находить эффективные пути решения проблем.

Если вы хотите углубить свои знания и применить их на практике, с алгоритмическими заданиями по графам вы можете ознакомиться в хендбуке по алгоритмическому программированию.

В нём рассматриваются такие важные темы, как поиск в ширину (BFS), поиск в глубину (DFS), обходы графа, алгоритм нахождения компонент связности в графе и многое другое. Это поможет вам освоить ключевые алгоритмы и применить теоретические знания на практике, делая ваши решения ещё более эффективными и продуманными.

А сейчас перейдём к квизам и задачам на закрепление материала.