2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 00:25 


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

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

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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 00:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 09:20 


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

-- 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$

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 11:51 


13/05/14
250
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$, в котором "Вес любого его внутреннего ребра не больше веса любого граничного ребра"?

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 14:11 


10/05/13
251
Да $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 --

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 14:44 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 15:13 


10/05/13
251
Возможны ребра с одинаковыми весами.

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 15:21 


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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 15:44 


10/05/13
251
Давайте я на всякий случай дам ссылку на источник задачи 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 писал(а):
Выбираем внутреннее ребро минимального веса. Удаляем одну из его вершин и получаем кандидата. Затем, из оставшихся внутренних рёбер выбираем ребро минимального веса, и удаляем одну из его вершин. Получим ещё одного кандидата. И так далее с некоторыми уточнениями.

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 17:55 


13/05/14
250
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)$
и так далее....

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 18:00 


10/05/13
251
sqribner48 в сообщении #974641 писал(а):
А если перейти от графа $G$ к его реберному графу $R$, в котором веса вершин равны весам соответствующих ребер.


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

-- 06.02.2015, 20:02 --

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

-- 06.02.2015, 20:41 --

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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 18:43 


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

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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 18:49 


10/05/13
251
test case - тестовый случай - пример

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 18:57 


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

 Профиль  
                  
 
 Re: Задача вроде бы на Минимальные Остовные Деревья
Сообщение06.02.2015, 19:38 
Заслуженный участник


22/11/10
1130
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 имеет "хорошую" учетную стоимость. Можно гуглить.
Ну, и несколько слов о том, что делать, когда есть ребра одинаковой стоимости. Да все то же самое. При просмотре инцидентных ребер они все сразу хором и добавляются к текущему подграфу. Однако есть риск несколько раз зарегистрировать один и тот же подграф, начиная с разных ребер одного веса. Здесь надо просто назначить расширенную операцию сравнения, которая при равенстве весов дополнительно сравнивает еще и номера ребер (ну или еще что, лишь бы обеспечить уникальность). При таком подходе каждый подграф будет описан только один раз.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу 1, 2, 3  След.

Модераторы: maxal, Karan, Toucan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group