2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Замыкание DAG (ориентированного ациклического графа)
Сообщение02.01.2015, 19:18 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Добрый день!

Предварительная задача.
Имеется направленный ациклический граф (достаточно разреженный, для определённости можно считать, что кол-во рёбер порядка $N\log N$, где $N$ - количество вершин графа).
К графу могут добавляться/убираться вершины/рёбра (без дублирования и нарушения ацикличности).
Необходимо быстро отвечать на вопрос связаны ли две вершины путём (в том числе, и для проверки ацикличности при добавлении нового ребра).
Напрашивается решение хранить предпосчитанными все пары вершин, связанных хотя бы одним путём (транзитивное замыкание).
При этом, для быстрого удаления ребра, нужно для каждой пары хранить количество путей их связывающих.

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

Вариант с хранением предпосчитанными всех путей выглядит неоптимальным.
Есть ли решения лучше?

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение02.01.2015, 20:30 
Аватара пользователя


14/10/13
339
Цитата:
после чего все пути, проходящие через эту пару вершин считаются недействительными
Это значит - пути, содержащие ребро, связывающее эти две вершины?

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение02.01.2015, 20:52 
Заслуженный участник
Аватара пользователя


01/09/13
4318
popolznev в сообщении #955571 писал(а):
Цитата:
после чего все пути, проходящие через эту пару вершин считаются недействительными
Это значит - пути, содержащие ребро, связывающее эти две вершины?

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

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение02.01.2015, 21:10 


01/12/11

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

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение02.01.2015, 22:01 
Заслуженный участник


27/04/09
28128
Skeptic в сообщении #955591 писал(а):
Попробуйте хранить самые длинные пути.
И что с ними делать при добавлении ребра к вершине, входящей в «выключенный»? Если хранить все пути, можно будет новые посчитать без особых проблем (кажется).

Geen в сообщении #955533 писал(а):
При этом, для быстрого удаления ребра, нужно для каждой пары хранить количество путей их связывающих.
А как это хранение при удалении ребра обновлять быстрее, чем обновлять транзитивное замыкание?

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение02.01.2015, 23:55 
Заслуженный участник
Аватара пользователя


01/09/13
4318
arseniiv в сообщении #955616 писал(а):
Geen в сообщении #955533 писал(а):
При этом, для быстрого удаления ребра, нужно для каждой пары хранить количество путей их связывающих.
А как это хранение при удалении ребра обновлять быстрее, чем обновлять транзитивное замыкание?

Обозначим ребро от вершины a до вершины b как (ab), множество вершин, из которых достижима вершина a через U(a), множество вершин которые достижимы из вершины b как D(b). Сами вершины тоже входят в соответствующие мн-ва. Элементы соответствующих мн-в обозначаем буквой в нижнем регистре (например, $u(a)\in U(a)$). Кол-во путей от c к d обозначим $P(c,d)$ ($\forall x P(x,x)=1$). Тогда, добавление ребра (ab) приводит к следующим изменениям кол-ва путей: $P'(u(a),d(b))=P(u(a),d(b))+P(u(a),a) P(b,d(b))$. Остальные "счётчики" остаются неизменными. Удаление ребра приводит к обратному изменению "счётчиков". При этом, $P(c,d)=0$, очевидно, эквивалентно отсутствию путей, и такие пары можно просто не хранить/удалять.

-- 03.01.2015, 01:28 --

Есть две идеи, которые я пока не знаю как (можно ли) развить.
1. Рёбра, входящие в вершину b можно интепретировать как операцию объединения: $U(b)=\{b\}\cup\bigcup_a U(a)$. Тогда, пометка пары вершин (cb) будет означать $U(b)=\{b\}\cup\bigcup_a U(a)\backslash U(c)$
2. Считать, что рёбра имеют цвет и пометка пары вершин означает, например, добавление чёрного ребра. Соответсвенно, как-то вести учёт моно/полихромных путей.

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение12.01.2015, 01:43 
Заслуженный участник


27/04/09
28128
Geen в сообщении #955651 писал(а):
Удаление ребра приводит к обратному изменению "счётчиков".
Хм, точно…

Geen в сообщении #955651 писал(а):
2. Считать, что рёбра имеют цвет и пометка пары вершин означает, например, добавление чёрного ребра. Соответсвенно, как-то вести учёт моно/полихромных путей.
Видимо, можно вести достаточно прямо: $P_k(a,b)$ — количество путей, содержащих хотя бы одно ребро цвета $k$. Как будто считаться должно не сильно сложнее. И, если так, это замечательное решение (и вряд ли упрощаемое)!

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение14.01.2015, 19:32 
Заслуженный участник
Аватара пользователя


01/09/13
4318
arseniiv в сообщении #960316 писал(а):
Видимо, можно вести достаточно прямо: $P_k(a,b)$ — количество путей, содержащих хотя бы одно ребро цвета $k$. Как будто считаться должно не сильно сложнее.

К сожалению, я не нашёл как это применить к исходной задаче...

 Профиль  
                  
 
 Re: Замыкание DAG
Сообщение15.01.2015, 15:42 
Заслуженный участник


27/04/09
28128
Как же? Вы ведь сами писали:
Geen в сообщении #955651 писал(а):
Считать, что рёбра имеют цвет и пометка пары вершин означает, например, добавление чёрного ребра.

Тогда если $P_\text{ч}(c,d) = P(c,d)$, все пути из $c$ в $d$ содержат хоть одно чёрное ребро, и потому переход $c\to d$ заблокирован. Ну а если $P_\text{ч}(c,d) < P(c,d)$, пути ещё есть.

Вообще, я сначала понял слова «добавление чёрного ребра» как предварительное удаление исходного и потом уже добавление чёрного. Такая смена цвета не изменит соответствующие $P$, но изменит $P_\text{ч}$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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