Два наименьших остовных дерева

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

0

хорошая задачка, интересная
хочется понять не только поиск 2ого, а в принципе n-го минимального остова

склоняюсь к NP (вроде здесь нет релаксации), но, возможно, есть красивое какое-то решение

0

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

0

Мне кажется это задачка в три хода.

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

0

1. Рассмотрим наименьшее остовное дерево t1 и остовное дерево t2, полученное заменой одного из ребер r1 дерева t1 на другое ребро r2 с наименьшей разницей весов (с разницей от 0 и более). Пока мы не знаем, является ли второе дерево t2 вторым минимальным, но оно минимально из тех, которые отличаются только одним ребром, по определению.

2. Рассмотрим еще третье дерево t3, которое будет отличаться от первого дерева t1 как минимум одним ребром и еще одним ребром (как минимум одним), так как второе дерево t2 самое лучшее из тех, которые отличаются от первого дерева одним ребром. Будем доказывать, что дерево t3 не лучше t2.

3. Если третье дерево t3 отличается от второго t2 ровно одним ребром (то есть дерево t3 содержит ребро r2), то дерево t3 не будет лучше, чем t2.

... Продолжение следует ...

Добавлено через 7 минут
4. Из п.3 следует, что t3 должно отличаться от t2 как минимум двумя ребрами, чтобы быть "минимальнее", и при этом, соответственно, не содержит ребро r2. При этом t3 может содержать ребро r1, например, но тогда от дерева t1 все равно должно отличаться двумя и более ребрами.

0

Сообщение от Mikhaylo то дерево t3 не будет лучше, чем t2.

так по условиям это и не требуется. если их общий вес будет одинаковым, они все равно останутся минимальными.

0

Сообщение от vantfiles Мне кажется это задачка в три хода. Находим любым известным алгоритмом минимальное остовное дерево. Удаляем из графа ребро с минимальным весом так, чтобы граф остался связным. Находим любым известным алгоритмом минимальное остовное дерево.

Вряд ли это будет работать.

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

0

Сообщение от TheCalligrapher если бы мы вместо этого заменили

А разве по условию мы можем что-то менять в исходном графе?

Сообщение от TheCalligrapher Вряд ли это будет работать.

Будет. Набросайте кучу примеров и сами посмотрите, что будет получаться.

0

Сообщение от vantfiles А разве по условию мы можем что-то менять в исходном графе?

Ым... Простите, а "удаляем из графа ребро с минимальным весом так, чтобы граф остался связным" в сообщении #4 - это чьи слова?

Сообщение от vantfiles Будет. Набросайте кучу примеров и сами посмотрите, что будет получаться.

Нет, не будет. Выше я описал, как построить пример, на котором ничего получаться не будет. Достаточно одного примера.

Граф K4 c картинки. Минимальное дерево 1+1000+1001=2002. Если по вашему предложению исключить ребро 1 из рассмотрения, то получим минимальное дерево 1000+1001+1002=3003. А это - не второе дерево. Второе дерево - это например 1+1001+1002=2004.

Теперь понятно?

Миниатюры

 

0

Сообщение от TheCalligrapher Теперь понятно?

согласен. кумекаем дальше.

0

Сообщение от vantfiles Мне кажется это задачка в три хода. Находим любым известным алгоритмом минимальное остовное дерево. Удаляем из графа ребро с минимальным весом так, чтобы граф остался связным. Находим любым известным алгоритмом минимальное остовное дерево.

По крайней мере, это доказывает, что задачу можно решить без полного перебора, т.е. задача не NP.

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

0

Сообщение от vrm2 Нужно по-очереди пробовать удалять каждое из ребер первого дерева, и строить новое дерево. Затем выбрать из полученных деревьев минимальное. Это сработает, т.к. обязательно существует ребро, которое присутствует в первом дереве, но отсутствует во втором.

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

0

Вариант который приходит на ум:
Строим минимальное оставное дерево
По очереди из графа удаляем по одному ребру данного дерева (при условии что граф остается связанным)
Каждый раз находим по новому графу минимальное оставное дерево (получим n-1 новых деревьев)
Выбираем из полученных деревьев минимальное, оно может совпадать по размеру с исходным минимальным (если есть несколько одинаковых по размеру разных минимальных деревьев)

По сути это перебор и не решается задача нахождения n-го минимального дерева.

1