Задача вроде бы на Минимальные Остовные Деревья

[frankenstein]

Дан взвешенный неориентированный связный граф без петель и кратных ребер.
Определим множество $A$ как множество вершин этого графа, которое содержит как минимум две его вершины.

Если множеству $A$ принадлежат вершины $u$ и $v$, то во множество так же
входит и ребро $(u, v)$, такое ребро назовем внутренним.
Ребро, одна из вершин которой входит во множество $A$, а другое нет - назовем граничным.

Множество вершин $B$ - называют кандидатом, если:
1. Его вершины связны (т. е. из каждой вершины существует путь в другую в данном графе)
2. Вес любого его внутреннего ребра больше веса любого граничного ребра.

Надо определить сумму мощностей всевозможных кандидатов заданного графа.
Ну, вот. Как-то перевел условие задачи .
Не знаю как подобраться к решению задачи, перебор не сработает так как граф имеет до $5000$ вершин.
Уверен что задача связана с проблемой Мин. Остовных Деревьев.
Еще мой один шаг к решению - сам граф является кандидатом, так как он связный по условию задачи и у него вообще
нет граничных ребер, получается ответом будет некое число неменьшее мощности множества вершин данного графа.

[arseniiv]

У вас всё-таки множества вершин или полноценные подграфы? Правда, в подграф всё равно не может входить ребро, у которого в этот подграф входит только одна из инцидентных ему вершин — должны обе (хотя специально для задачи, конечно, можно…). А ещё что здесь понимать под мощностью подграфа — видимо, сумму весов входящих рёбер?

[frankenstein]

Тут нигде не сказано "мощность подграфа" или что-то в этом роде, тут есть выражение "мощность всевозможных кандидатов", а кандитат - как мы определили это множество. Мощность кандидата - количество входящих в него вершин.

-- 06.02.2015, 11:46 --

Вообще можно сказать так:
Множесво вершин $B$ называют кандидатом, если

$$ | B | \ge 2 $$

и
Если из любой вершины в $B$ можно добраться до любой другой из $B$ по
данному графу.
и

$$ \forall{u, v} \in B \nexists{a} \in \{p(u) \setminus B\} : w(u, a) \ge minw(B) $$

и то же самое для окрестности $v$

Здесь под$p(a)$ определено множество смежных вершин вершины $a$.
$minw(B)$ минимальный вес ребра, вершины которого есть в $B$

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

[sqribner48]

frankenstein
1. Мне кажется, что все-таки кандидат - это не просто множество вершин, а подграф т.к. вместе с любой парой вершин $u$ и $v$ он, по-определению, содержит и ребро $(u,v)$, соединяющее эти вершины. (А мощность графа (подграфа) это количество его вершин).
2. В Вашем последнем выражении более целесообразно было бы вместо $p(u)$ использовать общепринятое выражение для окрестности $N(u)$. Тогда было бы

$$\forall {u,v} \in B \nexists {a} \in \{N(u) \setminus B\} \colon w(u,a) \ge \min w(B).$$

Не совсем понятно, что такое $\min w(B)$, ведь $w$ определена на ребрах (а не на множестве вершин). Кроме того, почему в правой части выражения стоит $\min w(B)$, (а не $\max w(B)$). Ведь по Вашему определению любое внутренне ребро имеет больший вес, чем смежное с ним внешнее ребро.
3. И, наконец, Вы написали "Задача вроде бы на Минимальные Остовные Деревья". Но тогда, по логике, не следовало бы рассматривать кандидат $B$, в котором "Вес любого его внутреннего ребра не больше веса любого граничного ребра"?

[frankenstein]

Да $B$ это подграф.
Все верно: "Вес любого внутреннего ребра $B$ должен быть больше веса любого его граничного ребра"

-- 06.02.2015, 16:17 --

$$\forall {u,v} \in B \nexists {a} \in \{N(u) \setminus B\} \colon w(u,a) \ge \min\{ w(x, y) : x, y \in B \}.$$

Вот более правильное условие.

-- 06.02.2015, 16:24 --

Задача на Минимальные Остовные Деревья - моя догадка, просто я считаю, что
если построить Максимальный или Минимальный Остов дерева - это поможет решению
задачи.

[sup]

Эта задача уж скорее просто на использование приоритетной очереди. Что-то типа алгоритма Прима для остовных деревьев (растущее дерево).
Пусть $B$ - множество-кандидат. Рассмотрим в нем самое дорогое ребро. Граничные к нему уж точно должны быть не дороже этого. Далее организуем приоритетную очередь и начинаем добавлять по одному ребру.

(чуть больше деталей)

Добавляем ребро и все новые внутренние, которые появились после добавления новой вершины. Корректируем очередь. После этого проверяем корректность полученного графа. И тд. Если возникнет ребро дороже самого первого - процесс обрываем.
На этом пути можно перечислить все графы-кандидаты.

[frankenstein]

Возможны ребра с одинаковыми весами.

[Skeptic]

Выбираем внутреннее ребро минимального веса. Удаляем одну из его вершин и получаем кандидата. Затем, из оставшихся внутренних рёбер выбираем ребро минимального веса, и удаляем одну из его вершин. Получим ещё одного кандидата. И так далее с некоторыми уточнениями.

[frankenstein]

Давайте я на всякий случай дам ссылку на источник задачи http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3706

-- 06.02.2015, 17:44 --

Там есть примеры.

-- 06.02.2015, 17:45 --

Skeptic в сообщении #974576 писал(а):

Выбираем внутреннее ребро минимального веса. Удаляем одну из его вершин и получаем кандидата. Затем, из оставшихся внутренних рёбер выбираем ребро минимального веса, и удаляем одну из его вершин. Получим ещё одного кандидата. И так далее с некоторыми уточнениями.

А если после удаления вершины очередного ребра вы получите несвязный граф?

[sqribner48]

frankenstein

sup в сообщении #974564 писал(а):

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

Мне кажется что эта процедура может значительно усложнить работу программы.
В порядке гипотезы:
А если перейти от графа $G$ к его реберному графу $R$, в котором веса вершин равны весам соответствующих ребер. Тогда надо будет искать подграфы с максимальной суммой весов вершин.
Скажем так:
1. выбрать вершину $v$ с максимальным весом;
2. проверить смежные с ней вершины из $N(v)$; вершины с меньшим весом далее не рассматривать;
3. перейти к одной из оставшихся вершин с весами, равными весу исходной вершины; например к вершине $u \in N(v)$ для которой $w(u) = w(v)$.
4. проверить смежные с $u$ вершины из $N(u)$, если все смежные вершины имеют не больший вес т.е.
$\forall x \in N(u) \; w(x) \le w(u)$, то добавить ее в кандидат, в противном случае перейти к с следующей вершине из $N(v)$
и так далее....

[frankenstein]

sqribner48 в сообщении #974641 писал(а):

А если перейти от графа $G$ к его реберному графу $R$, в котором веса вершин равны весам соответствующих ребер.

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

-- 06.02.2015, 20:02 --

А что-то не догоняю, уточните как вы определяете вес вершины?

-- 06.02.2015, 20:41 --

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

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

[sqribner48]

Реберный граф $L(G)$ графа $G$ это такой граф, в котором вершинами являются ребра графа $G$ и две вершины графа $L(G)$ смежны тогда и только тогда, когда смежны соответствующие им ребра графа $G$ (это из Харари).
Я просто подумал, что если исходный граф $G$ разреженный, тогда это может "прокатить". А что по этому поводу скажет уважаемый sup?

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

[frankenstein]

test case - тестовый случай - пример

[sqribner48]

Спасибо. А исходный файл с входными данными задачи там выложен? Хотелось бы узнать какой граф $G$ разреженный или нет.
Сейчас мне показалось, что эта задача сводится к нахождению всех подграфов, у которых удвоенная сумма весов внутренних ребер не меньше чем сумма весов "выходящих наружу" ребер.
P.S. рисунки получились какие-то обрезанные по краям.

[sup]

sqribner48 в сообщении #974641 писал(а):

1. выбрать вершину $v$ с максимальным весом;
2. проверить смежные с ней вершины из $N(v)$; вершины с меньшим весом далее не рассматривать;
3. перейти к одной из оставшихся вершин с весами, равными весу исходной вершины; например к вершине $u \in N(v)$ для которой $w(u) = w(v)$.
4. проверить смежные с $u$ вершины из $N(u)$, если все смежные вершины имеют не больший вес т.е.
...

Надо думать, здесь речь идет о вершинах реберного графа.
Пункт 2 в части "... далее не рассматривать ..." сомнителен. Можно привести примеры, когда они все же участвуют в графе-кандидате.
А в целом, для такого поиска как раз и нужна приоритетная очередь. Очень удобно.

sqribner48 в сообщении #974660 писал(а):

А что по этому поводу скажет уважаемый sup ?

Если я правильно понимаю задачу, то нам дан граф $G$ и требуется описать такие связные подграфы $B$, что всякое внутреннее ребро подграфа $B$ дороже всякого внешнего.
Я намерен систематически перечислить все такие подграфы.
Сначала, для простоты, предположим, что все веса разные. Это будет, так сказать, главная колея алгоритма.
В каждом искомом подграфе $B$ всегда имеется самое дорогое ребро. Поэтому мы сгруппируем все искомые $B$ по этому ребру. Итак, циклом пробегаем все ребра и находим все $B$, для которых оно самое дорогое.
Возникла подзадача.
Пусть дано некое ребро. Опишем все подграфы $B$, для которых это самое дорогое ребро. Для определенности обозначим его как $(0,1)$ - ребро между вершинами 0 и 1. Его вес - $W_0$.
Рассмотрим семейство $K$ всех ребер, инцидентных вершинам 0 и 1. Если среди них найдется хотя бы одно дороже $W_0$ - работа закончена. Таких $B$ нет. А если они все меньше? Тогда вот и первый кандидат. $B$ - состоит из единственного ребра $(0,1)$. Дальше. Рассматриваем самое дорогое ребро в семействе $K$. Оно непременно будет или внутренним или внешним к нашему искомому $B$. А значит просто обязано быть внутренним. Ну что-ж, добавляем. к нашему ребру $(0,1)$. Пусть для определенности это $(0,2)$ и вес - $W_1$. Но вместе с ним у нас появляется и внутреннее ребро $(1,2)$ с весом $W_2$. Проверяем полученный граф на предмет допустимости. Если допустим - в копилку и поехали дальше. А если нет? Это значит, что в семействе $K$ есть ребра дороже $W_2$, а значит все они с необходимостью должны быть внутренними. Добавляем их все чохом (а вместе с ними и кучу других "индуцированных" внутренних). И вновь проверяем полученный подграф. Если допустим - в копилку, а если нет, то ... Надеюсь, дальнейшее уже очевидно. Отмечу лишь, что как только мы натыкаемся на ребро дороже $W_0$ процедура обрывается.
Как лучше всего проводить поиск таких ребер? Такая структура давным-давно известна - приоритетная очередь из алгоритма Прима. Там есть всякие навороты, типа фибоначчиевы кучи и прочие изыски, для которых операция updateKey имеет "хорошую" учетную стоимость. Можно гуглить.
Ну, и несколько слов о том, что делать, когда есть ребра одинаковой стоимости. Да все то же самое. При просмотре инцидентных ребер они все сразу хором и добавляются к текущему подграфу. Однако есть риск несколько раз зарегистрировать один и тот же подграф, начиная с разных ребер одного веса. Здесь надо просто назначить расширенную операцию сравнения, которая при равенстве весов дополнительно сравнивает еще и номера ребер (ну или еще что, лишь бы обеспечить уникальность). При таком подходе каждый подграф будет описан только один раз.