§ 58. Каркасы минимального веса

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

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

Вес каркаса — сумма весов всех рёбер, вошедших в него. Если каждому ребру приписана стоимость, длина или иной числовой показатель, его вес учитывают при сложении. Так можно оценить затраты на выбранную систему соединений. Например, для рёбер с весами 2, 4 и 7 вес каркаса равен 2 + 4 + 7 = 13.

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

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

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

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

У дерева с n вершинами ровно n−1 ребро. Это можно понять по построению: начинаем с одной вершины, а затем каждое новое ребро присоединяет к уже собранной части одну новую вершину. Чтобы добавить остальные n−1 вершин, нужно ровно n−1 такое присоединение. Если рёбер окажется меньше, хотя бы одна вершина не присоединится; если добавить лишнее между уже соединёнными вершинами, появится цикл.

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

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

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

Свойства каркаса и каркаса минимального веса

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

Разбор задач

Задача 1. В связном графе с вершинами A, B, C и D выбраны рёбра AB, BC и CD. Нужно проверить, является ли этот набор каркасом. Весов рёбер нет, поэтому проверяем только свойства дерева. Важно не спутать каркас с любым подграфом: он обязан включать все четыре вершины и соединять их.

1. Сверяем вершины: A, B, C и D присутствуют, значит, все вершины исходного графа охвачены.
2. Проверяем связность: из A можно пройти к D по цепочке A—B—C—D, поэтому все вершины соединены.
3. Считаем рёбра: их три, а для n = 4 должно быть n−1 = 3. Цепочка не возвращается к начальной вершине, значит, цикла нет.

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

Задача 2. У графа три вершины A, B, C и рёбра AB веса 1, AC веса 2, BC веса 4. Требуется перебрать каркасы и выбрать каркас минимального веса. Для трёх вершин каркас должен содержать два ребра. Здесь любой выбор двух рёбер соединяет все вершины и не образует цикла.

1. Перечисляем варианты: AB и AC дают вес 1 + 2 = 3; AB и BC дают 1 + 4 = 5.
2. Оставшийся вариант — AC и BC, его вес равен 2 + 4 = 6. Каждый набор содержит две вершины-связи, соединяющие все три вершины.
3. Сравниваем суммы 3, 5 и 6. Наименьшая сумма равна 3, поэтому выбираем рёбра AB и AC.

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

Задача 3. Дана таблица рёбер: AB — 1, BC — 2, AC — 3, CD — 4, BD — 5. Нужно построить каркас минимального веса жадным способом. В графе четыре вершины, значит, для готового дерева потребуется три ребра. Сначала упорядочим рёбра, а затем будем следить, не соединены ли уже концы очередного ребра выбранным путём.

1. Порядок по возрастанию: AB (1), BC (2), AC (3), CD (4), BD (5). Добавляем AB и BC: они соединяют новые части и пока не образуют цикл.
2. Ребро AC пропускаем: A и C уже соединены путём A—B—C, поэтому оно замкнуло бы цикл. Добавляем CD, так как вершина D ещё не присоединена.
3. Выбрано три ребра, то есть n−1. Все вершины связаны, цикла нет; сумма весов равна 1 + 2 + 4 = 7.

Ответ: каркас минимального веса включает AB, BC и CD, его вес равен 7. Ребро BD уже не требуется для каркаса, а AC нельзя добавлять, поскольку оно создаёт цикл. Алгоритм остановился, когда все четыре вершины оказались соединены деревом.

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

• Выбирать только самые лёгкие рёбра без проверки циклов. Так можно получить цикл, потратив рёбра на уже существующую связь, и не присоединить все вершины. Ошибка возникает, когда вес считают единственным условием выбора. Проверяй, есть ли между концами ребра путь по уже выбранным рёбрам; если есть, пропускай его.
• Остановиться до включения всех вершин. Набор рёбер может быть деревом, но не каркасом исходного графа, если какая-то вершина осталась в стороне. Это случается, когда считают только число рёбер, не сверяясь с вершинами. Перед завершением проверь, что включены все вершины и каждая достижима из остальных.
• Считать, что каркас обязан содержать все рёбра исходного графа. Тогда в нём могут появиться циклы, а само понятие каркаса потеряет смысл. Такое заблуждение возникает из-за смешения исходного графа и его подграфа. Сверь выбранные рёбра с условиями: все вершины сохранены, связность есть, циклов нет.
• Путать минимальное число рёбер с минимальным весом. У всех каркасов одного связного графа с n вершинами одинаковое число рёбер — n−1, но суммы весов могут различаться. Число рёбер отвечает за устройство дерева, а минимальность — за сравнение весов. Для самопроверки сложи веса каждого подходящего набора или применяй жадный выбор с проверкой циклов.

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

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

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

• Каркас содержит все вершины связного графа.
• Каркас является деревом: он связен и не содержит циклов.
• В каркасе на n вершинах ровно n−1 ребро.
• Вес каркаса равен сумме весов его рёбер.
• Каркас минимального веса имеет наименьшую такую сумму.
• При жадном построении ребро, создающее цикл, не добавляют.