Информатика · объяснение и практика

Чем минимальное остовное дерево отличается от кратчайших путей

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

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

Сумма сети и длина маршрута — разные величины

В учебной сети три узла А, Б и В. Связи А—Б и Б—В стоят по четыре единицы, прямая связь А—В стоит семь. Чтобы соединить все узлы с минимальной общей стоимостью, достаточно двух связей по четыре: итог восемь. Прямая связь за семь остаётся за пределами выбранного остова.

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

Как наращивать остов без лишнего цикла

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

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

Пример

Четыре вершины образуют квадрат; каждое из четырёх рёбер имеет вес 2, диагоналей нет. Какова стоимость минимального остова?

Можно удалить любое одно ребро квадрата. Останется связная цепочка из трёх рёбер суммарного веса 6. Меньше трёх рёбер четыре вершины деревом не соединить; выбор удалённого ребра неединственен.

Уточните входные ограничения

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

Ориентированная сеть требует другой постановки, поскольку связь А→Б не позволяет автоматически двигаться обратно. Также остов не учитывает резервирование на случай поломки: удаление одного его ребра разрывает связность. Если задача требует два независимых маршрута, одной минимальной суммы дерева недостаточно. Перед вычислением выпишите, какие именно требования предъявлены к выбранному подграфу.

От чтения к действию

А теперь — вы

В треугольнике Х—У и У—Я имеют вес 3, Х—Я — вес 5. Какова сумма минимального остова?

Частые вопросы

Остов всегда даёт кратчайший путь между любыми узлами?

Нет. Он минимизирует сумму выбранных рёбер. Внутренний путь дерева может быть длиннее пути, доступного в исходном графе.

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

При равных весах разные наборы рёбер могут соединять все вершины с одной и той же минимальной суммой.

Углублённый разбор

Обмен базисов объясняет жадный алгоритм в матроиде

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

Перед началом: Линейная независимость; Жадный выбор.

Наследственность сама по себе недостаточна

Конечная система (E,I) содержит пустое множество и вместе с каждым допустимым множеством содержит все его подмножества. Для матроида дополнительно требуется обмен: если A,B∈I и |A|<|B|, существует b∈B\A с A∪{b}∈I. Это сравнение размеров, а не суммарных весов. Оно заставляет все максимальные по включению независимые множества иметь одинаковый размер, называемый рангом.

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

Обмен оправдывает порядок по весам

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

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

Отказ обмена объясняет конкретный провал

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

Максимально весомые независимые векторы

Условие. В R² даны a=(1,0),b=(0,1),c=(1,1),d=(2,2) с весами 8,7,10,9. Найдите оптимальный независимый набор жадно и сравните с системой паросочетаний на трёхрёберном пути с весами 2,3,2.

  1. Сортировка векторов даёт c,d,a,b. Берём c веса 10. Вектор d=2c линейно зависим с ним, поэтому пропускаем.
  2. Добавляем a веса 8: det(c,a)=−1≠0. Ранг уже 2, поэтому b добавить нельзя. Получены {c,a} и вес 18.
  3. Независимый перебор пар подтверждает максимум 18: пара c,d недопустима; остальные имеют веса 15,18,17,17,16. Одиночные наборы имеют меньший вес.
  4. Для пути жадность берёт среднее ребро веса 3 и блокирует оба внешних. Их пара имеет вес 4. Отсутствие обмена между средним одиночным и внешней парой объясняет, почему здесь матроидная гарантия неприменима.

Ответ. Для векторов оптимум {c,a}, вес 18; для паросочетаний жадный вес 3 проигрывает допустимому весу 4.

Проверка. Все 16 подмножеств векторов проверены точными определителями и рангом. Все 8 подмножеств трёхрёберного пути отдельно проверены по общим концам; предъявлены конкретные A,B, нарушающие обмен.

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

Проверьте понимание

Каков максимальный вес независимого набора указанных векторов?

Вопросы к этой главе

Почему после выбора двух независимых векторов не рассматривается третье добавление?

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

Зависит ли оптимальность от порядка элементов одинакового веса?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • David Barrington: CMPSCI611 Lecture5, Matroid Theorem

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

Следующий по весу остов и максимальное ребро фундаментального цикла

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

Перед началом: Минимальное остовное дерево; Единственный путь и фундаментальный цикл дерева.

Другой набор рёбер и другая стоимость — разные требования

Зафиксируем минимальный остов T связного неориентированного графа. Добавление любого ребра e вне T создаёт единственный цикл: ребро e вместе с путём между его концами в T. Удалив с этого пути любое ребро f, снова получаем остов. Его вес изменяется на w(e)−w(f). Отрицательное изменение невозможно, иначе T не было минимальным.

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

Для положительного обмена нужен наибольший меньший вес

Для каждого e ищем на его древесном пути самое тяжёлое ребро, вес которого строго меньше w(e). Его удаление даёт наименьшее положительное изменение среди обменов с этим e. Если w(e) больше максимума пути, достаточно обычного максимума. Если равно максимуму, нужен следующий различный вес. Если меньшего веса нет, это ребро даёт только нулевые обмены.

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

Равенства нельзя уничтожать искусственным возмущением задачи

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

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

Нулевой обмен скрывает лучшее положительное увеличение

Условие. Рёбра графа: AB=1, BC=1, AC=1, CD=2, BD=2, AD=4. Зафиксирован минимальный остов T={AB,BC,CD} веса 4. Найдите наименьшую стоимость остова строго больше 4.

  1. Минимальность T следует из двух обязательных соединений внутри тройки A,B,C весом не меньше 2 и связи с D весом не меньше 2. Его стоимость 4 достигает этой нижней границы.
  2. Добавление AC создаёт цикл из трёх единичных рёбер. Любой разрешённый обмен имеет увеличение 0, поэтому новой различной стоимости здесь нет.
  3. При добавлении BD древесный путь B–C–D имеет веса 1 и 2. Удаление CD веса 2 даёт ещё один минимум, но удаление BC веса 1 даёт увеличение 1.
  4. Остов {AB,BD,CD} имеет вес 1+2+2=5. Добавление AD даёт минимальное увеличение 4−2=2 и кандидат веса 6.
  5. Минимальное положительное увеличение равно 1. Поэтому строго следующая стоимость равна 5. Правило «брать только максимум пути и отбрасывать нули» ошибочно вернуло бы 6.

Ответ. Другая минимальная структура может стоить 4; строго следующая различная стоимость равна 5.

Проверка. Полный перебор 20 трёхрёберных подмножеств проверяет связность и выделяет все остовы. Наименьшая стоимость равна 4, а минимум среди стоимостей больше 4 равен 5.

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

Проверьте понимание

Какова строго следующая после 4 различная стоимость остова в разобранном графе?

Вопросы к этой главе

Почему нельзя просто запретить одно ребро найденного остова?

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

Что вернуть, если положительных обменов нет?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • CP-Algorithms: Second best Minimum Spanning Tree

    Документация авторской реализации однообменного поиска по фундаментальному пути; хранение двух различных максимальных весов для обработки совпадающих весов.

Минимальное ориентированное остовное дерево требует стягивания цикла

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

Перед началом: Ориентированная достижимость из корня; Суммарный вес остовного дерева.

Локальный минимум является нижней границей, но не всегда деревом

Конечный ориентированный взвешенный граф с фиксированным корнем r; ищется исходящая арборесценция: из r достижимы все вершины, у каждой другой ровно одна входящая дуга.

Сначала проверяют достижимость всех вершин из r: иначе исходящей арборесценции нет. Дуги, входящие в r, не выбираются. Для каждой другой вершины v берём входящую дугу минимального веса m(v). Любая арборесценция содержит один вход в v, поэтому сумма m(v) является нижней границей стоимости.

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

Вход в цикл заменяет конкретную выбранную дугу

Пусть C — цикл выбранных дуг. При внешнем входе u→v, где v∈C, старый вход в v удаляется. Если временно оплачены все внутренние дуги цикла, дополнительная цена такого решения равна w(u,v)−m(v). Именно её ставят на дугу входа в сжатую супервершину; исходную точку v сохраняют для раскрытия.

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

Ориентация и восстановление входят в проверку ответа

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

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

Более тяжёлый внешний вход дешевле после замены

Условие. Корень r, остальные вершины a,b,c,d. Дуги r→a:5,r→b:6,r→c:8,r→d:9,c→a:1,a→b:4,b→c:2,c→d:3,a→d:7. Найдите минимальную исходящую арборесценцию.

  1. Минимальные входы: c→a веса 1, a→b веса 4, b→c веса 2 и c→d веса 3. Первые три образуют цикл abc; набор не достигается из r.
  2. Сжимаем abc. Стоимости входов из r становятся 5−1=4 в точку a, 6−4=2 в b, 8−2=6 в c. Хотя исходный вход r→a легче, наименьшая добавочная цена у r→b.
  3. В сжатой задаче выбираем r→C с ценой 2 и C→d с ценой 3. Возвращаем стоимость внутренних дуг цикла 1+4+2=7: общий результат 7+2+3=12.
  4. Раскрываем вход в b: удаляем a→b веса 4, оставляем b→c и c→a. Итоговые дуги r→b,b→c,c→a,c→d имеют исходные веса 6,2,1,3 и достигают все вершины.

Ответ. Минимальная стоимость равна 12; подходит арборесценция {r→b,b→c,c→a,c→d}.

Проверка. Независимый перебор 24 способов выбрать по одному входу каждой некорневой вершине отбрасывает недостижимые циклические наборы и даёт минимум 12. Вход r→a с сохранением остальных допустимых циклических дуг дал бы 14, поэтому сравнение исходных входов выбрало бы худший вариант.

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

Проверьте понимание

Какой внешний вход в цикл abc выбирается после корректировки стоимостей в разобранном примере?

Вопросы к этой главе

Почему при раскрытии удаляется a→b, а не самая тяжёлая произвольная дуга?

Новая r→b уже обеспечивает единственный вход в b. Удалить нужно прежний вход в эту же вершину; другое удаление оставило бы у b два входа и лишило бы входа другой узел.

Можно применить Краскала, забыв направления?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • CMU 15-850 — Min-Cost Arborescences, §2

    Нормировка стоимости выбранных дуг и стягивание направленного цикла. В конспекте деревья ориентированы к корню; здесь все направления последовательно обращены и используются входящие дуги. Пример и полный перебор рассчитаны отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться