§ 45. Задача о лесопарке

Определения и обозначения

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

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

Минимальное остовное дерево — остовное дерево с наименьшей суммой весов рёбер. Оно соединяет все объекты, но требует минимальной общей длины или стоимости дорожек. Именно его ищут в задаче о лесопарке.

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

Как это устроено

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

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

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

Задача о лесопарке сводится к поиску минимального остовного дерева. Требование связать все объекты означает, что нужен остов, а требование уменьшить общую длину означает, что он должен быть минимальным. Так практическая задача проектирования превращается в задачу на графе.

Для поиска рёбра сортируют по возрастанию веса и проверяют одно за другим. Самое короткое ребро добавляют, если его концы пока находятся в разных компонентах связности; иначе оно замкнёт уже существующий путь и его пропускают. После выбора n−1 подходящего ребра получается связная сеть без циклов, а жадное свойство алгоритма гарантирует минимальную общую стоимость.

Объекты и этапы решения задачи о лесопарке

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

Если ребро соединяет уже связанные между собой вершины, его не добавляют. Когда выбрано n−1 ребро и все вершины входят в одну компоненту, решение завершено.

Разбор задач

Задача 1

Даны четыре объекта лесопарка и длины всех возможных дорожек между ними. Требуется построить сеть минимальной общей длины. Числовые значения в условии не указаны, поэтому решение показываем на общем наборе рёбер.

1. Представьте объекты вершинами, дорожки — рёбрами, а их длины запишите как веса.
2. Отсортируйте все рёбра по возрастанию веса и проверяйте их в этом порядке.
3. Добавляйте ребро, если оно соединяет разные компоненты; остановитесь после трёх добавленных рёбер, потому что n−1 = 4−1.

Ответ: выбранные три дорожки образуют минимальное остовное дерево, если они связывают все четыре объекта и не образуют цикл. Их веса нужно сложить, чтобы получить общую длину сети.

Задача 2

Для пяти вершин дан список рёбер с весами. Нужно определить рёбра минимального остовного дерева. Здесь главное не просто выбрать четыре самых маленьких числа, а проверить, не соединяют ли они вершины, между которыми уже существует путь.

1. Упорядочьте список рёбер по возрастанию веса.
2. Последовательно просматривайте список: добавляйте ребро при соединении разных компонент, а ребро внутри одной компоненты пропускайте.
3. Остановитесь после четырёх принятых рёбер, так как для пяти вершин требуется n−1 = 4 ребра.

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

Задача 3

Некоторые дорожки запрещены, а для каждой разрешённой указана стоимость строительства. Требуется найти минимальную стоимость связной сети или установить, что соединение невозможно. Запрещённые дорожки просто не включают в граф.

1. Постройте граф только из разрешённых рёбер и отсортируйте их по стоимости.
2. Применяйте жадный выбор: принимайте ребро без цикла и пропускайте ребро, концы которого уже связаны.
3. После выбора n−1 ребра проверьте, входят ли все вершины в одну компоненту; если нет, продолжать построение нельзя.

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

Типичные ошибки

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

Попытка соединить каждую пару объектов. Так появляются лишние дорожки и циклы, а стоимость возрастает. Для самопроверки используйте правило: при n вершинах в остовном дереве должно быть ровно n−1 ребро.

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

Суммирование длин всех рассмотренных рёбер. В стоимость входят только дорожки, которые действительно добавлены в дерево, а пропущенные рёбра ничего не стоят. Сложите веса только выбранных рёбер и сравните их число с n−1.

Связь с другими темами

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

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

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

Что запомнить

• Лесопарк моделируют взвешенным графом.
• Нужно соединить все вершины с минимальной суммой весов рёбер.
• Искомая сеть является минимальным остовным деревом.
• Остовное дерево не содержит циклов.
• В дереве из n вершин ровно n−1 ребро.
• При жадном алгоритме рёбра рассматривают от меньшего веса к большему.
• Ребро добавляют только тогда, когда оно не создаёт цикл.