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

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

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

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

Вес каркаса — сумма весов всех рёбер, входящих в каркас. Например, если в него входят рёбра весом 2, 4 и 5, его вес равен 11. Сумма позволяет оценить общую длину, стоимость или время выбранной сети.

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

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

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

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

Алгоритм Краскала сначала располагает все рёбра по возрастанию веса. Затем он проверяет их по очереди: ребро добавляется, если его концы пока принадлежат разным связанным частям; если они уже соединены найденными рёбрами, добавление создало бы цикл. Так разные части постепенно объединяются, а когда выбрано n−1 ребро, получается каркас. Алгоритм требует, чтобы исходный граф был связным.

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

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

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

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

Разбор задач

Задача 1

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

1. Упорядочим рёбра: AB=1, BC=2, AC=3, BD=4, CD=5.
2. Добавим AB и BC: они соединяют A, B и C, не образуя цикл.
3. Проверим AC: вершины A и C уже связаны через B, поэтому это ребро создало бы цикл A–B–C–A; пропустим его.
4. Добавим BD=4: вершина D присоединится к построенной части. Теперь выбраны три ребра и соединены все вершины.
5. Сложим веса выбранных рёбер: 1 + 2 + 4 = 7.

Ответ: каркас состоит из AB, BC и BD, его вес равен 7. Ребро CD не требуется, поскольку после добавления BD все вершины уже связаны. Проверка количества даёт n−1 = 3 ребра.

Задача 2

Построим каркас Краскалом для графа с вершинами A, B, C, D, E и рёбрами AB=1, BC=1, CD=2, DE=2, AC=1, CE=3, BD=3. Здесь есть несколько рёбер одинакового веса, поэтому важно не предполагать, что ответ единственный. Отсортируем веса, а при совпадениях будем проверять цикл после каждого добавления.

1. Сначала рассмотрим рёбра веса 1: AB, BC, AC. Добавим AB и BC, а AC пропустим, поскольку A и C уже соединены путём A–B–C.
2. Затем рассмотрим CD=2 и DE=2. Оба ребра присоединяют новые вершины к связной части, поэтому добавим их.
3. Получены четыре ребра для пяти вершин: AB, BC, CD и DE. Все вершины связаны, циклов нет, значит, каркас готов.
4. Вычислим вес: 1 + 1 + 2 + 2 = 6. Если вместо BC выбрать AC и затем соединить B ребром BC, цикл нужно снова проверять, поэтому одного выбора равных весов недостаточно.

Ответ: один каркас минимального веса — AB, BC, CD, DE; его вес равен 6. Замена равных по весу рёбер может дать другой каркас той же стоимости. Решающее условие — связать все вершины, не оставив циклов.

Задача 3

Нужно спроектировать сеть дорог минимальной общей длины между населёнными пунктами A, B, C, D. По таблице расстояний заданы дороги AB=4, AC=2, AD=7, BC=1, BD=5, CD=3. Представим пункты вершинами, а возможные дороги — рёбрами с весами, равными расстояниям. Для наглядности применим алгоритм Прима, начав с A.

1. Включим A. Из него доступны AB=4, AC=2 и AD=7; выберем AC=2 как самое лёгкое ребро, ведущее наружу.
2. Теперь внутри построенной части A и C. На её границе доступны AB=4, AD=7, CB=1 и CD=3; выберем CB=1.
3. В части находятся A, B, C, а D ещё не включена. К ней ведут AD=7, BD=5 и CD=3, поэтому добавим CD=3.
4. Все четыре пункта соединены тремя дорогами. Общая длина равна 2 + 1 + 3 = 6.

Ответ: достаточно построить дороги AC, CB и CD общей длиной 6. Выбор проверяется тем, что каждый раз добавлялось самое короткое ребро на границе построенной части, а в конце включены все пункты. Такая сеть связывает населённые пункты без замкнутого маршрута.

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

Выбирать все самые дешёвые рёбра подряд, не проверяя циклы. Это кажется естественным способом уменьшить сумму, но лёгкие рёбра могут замкнуть цикл и не соединить отдалённую вершину. Проверяйте, были ли концы ребра связаны до его добавления; если да, Краскал это ребро пропускает.

Путать минимальный вес с минимальным числом рёбер. Можно решить, что нужно искать каркас с особенно малым количеством рёбер, хотя у любого каркаса графа с n вершинами уже ровно n−1 ребро. Сравнивают не число рёбер, а сумму их весов; проверка проста — сложите веса выбранных рёбер.

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

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

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

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

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

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