Викиконспекты - Вклад участника [ru]

Транзитивный остов

2012-04-12T20:31:16Z

109.188.174.176:

{{Определение
|definition=
'''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
}}

__TOC__
== Алгоритм для антисимметричных отношений ==
Для удобства представим отношение в виде графа: <tex> G = \left < V, E \right > </tex>. Его транзитивным остовом будет граф <tex> G^- = \left < V, E^- \right > </tex>.

Введём несколько обозначений:
* <tex> u \underset{G}{\longrightarrow} v </tex> — в графе <tex> G </tex> есть ребро из вершины <tex> u </tex> в <tex> v </tex>;
* <tex> u \underset{G}{\overset{*}{\longrightarrow}} v </tex> — в графе <tex> G </tex> есть путь (возможно, рёберно пустой) из вершины <tex> u </tex> в <tex> v </tex> (то есть вершина <tex> v </tex> достижима из <tex> u </tex>);
* <tex> u \underset{G}{\overset{+}{\longrightarrow}} v </tex> — в графе <tex> G </tex> есть рёберно непустой путь из вершины <tex> u </tex> в <tex> v </tex>.

Также введём определение транзитивного замыкания в терминах теории графов:
{{Определение
|definition=
'''Транзитивным замыканием''' графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V | i \underset{G}{\overset{*}{\longrightarrow}} j \right \} </tex>.
}}

Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\longrightarrow}} j \Longrightarrow i \neq j </tex>.

Докажем теорему, из которой следует алгоритм.

{{Теорема
|statement=
Пусть <tex> G^- = \left < V, E^- \right > </tex>. Тогда <tex> E^- = \left \{ (k, m) \in E \ | \ \forall l: [ k \underset{G}{\overset{*}{\longrightarrow}} l \wedge (l, m) \in E \Longrightarrow k = l ] \right \} </tex>
|proof=
Докажем, что <tex> E^- \subseteq \left \{ (k, m) \in E \ | \ \forall l: [ k \underset{G}{\overset{*}{\longrightarrow}} l \wedge (l, m) \in E \Longrightarrow k = l ] \right \}</tex>:

Пусть <tex> G^- </tex> уже построен. Пусть <tex> (k, m) \in E^- </tex>. Тогда <tex> k \neq m </tex> (так как иначе удаление ребра <tex> (k, m) </tex> из <tex> E^- </tex> приведёт к образованию меньшего графа с тем же транзитивным замыканием, что нарушает условие минимальности транзитивного остова). Поэтому по определению транзитивного остова <tex> k \underset{G}{\overset{+}{\longrightarrow}} m </tex>. Пусть <tex> l </tex> — вершина, для которой выполняется <tex> k \underset{G}{\overset{*}{\longrightarrow}} l \underset{G}{\longrightarrow} m </tex>. Докажем, что <tex> k = l </tex>, от противного. Пусть <tex> k \neq l </tex>. <tex> G </tex> ацикличен, поэтому <tex> l \neq m </tex>. Поскольку <tex> G^* = (G^-)^* </tex>, верно <tex> k \underset{G^-}{\overset{+}{\longrightarrow}} l \underset{G^-}{\overset{+}{\longrightarrow}} m </tex>. Поскольку <tex> G^- </tex> ацикличен, путь из <tex> k </tex> в <tex> l </tex> не может содержать ребра <tex> (k, m) </tex>. Аналогично путь из <tex> l </tex> в <tex> m </tex> не может содержать <tex> (k, m) </tex>. Поэтому в <tex> G^- </tex> существует путь из <tex> k </tex> в <tex> m </tex>, не содержащий в себе ребро <tex> (k, m) </tex>. Поэтому удаление <tex> (k, m) </tex> из <tex> E^- </tex> не изменит транзитивное замыкание, что противоречит условию минимальности <tex> E^- </tex>. Поэтому <tex> \forall l: [ k \underset{G}{\overset{*}{\longrightarrow}} l \wedge (l, m) \in E \Longrightarrow k = l ] </tex>. Поскольку <tex> k \underset{G}{\overset{+}{\longrightarrow}} m </tex>, существует такая вершина <tex> l </tex>, что <tex> k \underset{G}{\overset{*}{\longrightarrow}} l \underset{G}{\longrightarrow} m </tex>, что приводит к выводу, что <tex> (k, m) \in E </tex>.

Докажем, что <tex> \left \{ (k, m) \in E \ | \ \forall l: [ k \underset{G}{\overset{*}{\longrightarrow}} l \wedge (l, m) \in E \Longrightarrow k = l ] \right \} \subseteq E^- </tex>:

Предположим, что <tex> (k, m) \in E </tex> и <tex> \forall l: [ k \underset{G}{\overset{*}{\longrightarrow}} l \wedge (l, m) \in E \Longrightarrow k = l ] </tex>. Докажем от противного, пусть <tex> (k, m) \notin E^- </tex>. Поскольку <tex> G </tex> ацикличен, <tex> k \neq m </tex> и поэтому <tex> k \underset{G^-}{\overset{+}{\longrightarrow}} m </tex>. Поскольку <tex> (k, m) \notin E^- </tex>, существует вершина <tex> l </tex> такая, что <tex> k \underset{G^-}{\overset{*}{\longrightarrow}} l \underset{G^-}{\overset{*}{\longrightarrow}} m </tex> и <tex> k \neq l \neq m </tex>. Поэтому <tex> k \underset{G}{\overset{+}{\longrightarrow}} l \underset{G}{\overset{+}{\longrightarrow}} m </tex>. Поскольку <tex> G </tex> ацикличен, существует вершина <tex> l' \neq k </tex>, для которой выполняется <tex> k \underset{G}{\overset{+}{\longrightarrow}} l' \underset{G}{\longrightarrow} m </tex>, что противоречит нашему предположению.

Так как множества <tex> E^- </tex> и <tex> \left \{ (k, m) \in E \ | \ \forall l: [ k \underset{G}{\overset{*}{\longrightarrow}} l \wedge (l, m) \in E \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, что и требовалось доказать.
}}

=== Псевдокод ===
<tex> R^- </tex> = <tex> R </tex>
foreach <tex> a </tex> in <tex> X </tex>
foreach <tex> b </tex> in <tex> X </tex>
foreach <tex> c </tex> in <tex> X </tex>
if <tex> aRb </tex> and <tex> bRc </tex> and <tex> aRc </tex>
<tex> R^- </tex>.delete(pair(<tex> a </tex>, <tex> c </tex>))

== Источники ==
* [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction]
* [http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1987/1987-25.pdf J.A. La Poutré and J. van Leeuwen. «Maintenance of transitive closures and transitive reductions of graphs», 1987]

Обсуждение:Splay-дерево

2012-04-11T20:36:22Z

109.188.174.176:

: {{tick | ticked=1}} саморегулирующееся? o_O
: {{tick | ticked=1}} "Основной идей для сохранение "
: {{tick | ticked=1}} Сделать отдельный раздел "опреации", в него их запихать как подразделы
: {{tick | ticked=1}} добавить категории
: {{tick | ticked=1}} названия вершин в конспекте и на картинках совпадают чуть менее чем никак. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 19:23, 6 февраля 2012 (MSK)
: {{tick}} нормально офромить источники
:: Ссылку на статью надо оформлять как
:: Автор1, Автор2. Название статьи.
:: Также, кажется, эта статья есть в открытом доступе, значит, добавить на нее ссылку. Добавить ссылку хотя бы на википедию. На визуализатор, если есть.
::: Треш-статья все еще не убрана. Ссылку на английскую википедию добавь, да. Нужная тебе статья — первая ссылка по запросу «Tarjan splay tree» и первый референс в английской вики. Это Sleator, Daniel D.; Tarjan, Robert E. (1985), "Self-Adjusting Binary Search Trees". --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:49, 8 апреля 2012 (GST)
::: И вообще, почитай эту статью, в ней ни слова по сплей-деревья. Тебе другая статья нужна.
:: Сначала пишут «Википедия», потом название статьи. --[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)

: {{tick | ticked=1}} раздел «определение» убрать, из него все запихать в шапку.
: {{tick | ticked=1}} сплей-дерево — не самобалансируещееся, почитай определение сбалансированного дерева поиска. Баланс в нем не сохраняется.
: {{tick}} про операции
:: Как-то бредово выглядит в начале каждого подпункта название операции с ее аргументами. Либо напиши аргументы в заголовке, либо придумай что-то другое. Еще плохо выглядит написаение аргументов в техе, а остального - плейнтекстом. Либо все плейнтекстом, либо все в техе и заюзать \operatorname
::: Сначала пишут структуру, потом — аргументы (Split(Tree, key) и т.п.). Ну и либо пиши Tree везде(в Find) тоже, либо там где не надо, не пиши.
:: Move to root — не операция, это одна из возможных эвристик, но которая не приводит ни к чему хорошему. Ее хорошо упомянуть, но не в операциях.
::: Теперь она вообще внезапно появляется и неясно зачем. Почитай немного статью, которую я сказал и пойми, где тебе будет уместно упомянуть её и как.
:::: Все еще не исправлено. И про нее написан полнейший бред, почитай уже статью Тарьяна. --[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)
{{tick}}В Splay нумерации списка нет, пункты 1, 1 и 1. Там же надо написать, что удаляешь вершину b, потому что сначала неясно. А вообще вершинам на картинках лучше бы чуть более осмысленные имена, например, x, p(parent) и g(grandparent). --[[Участник:Dgerasimov|Дмитрий Герасимов]] 01:48, 7 апреля 2012 (GST)
: Да, в лемме тоже неплохо бы переименовать. И в тех в статье выделить x, p и g, да.--[[Служебная:Contributions/109.188.174.176|109.188.174.176]] 00:36, 12 апреля 2012 (GST)
{{tick|ticked=1}}Я имею в виду, что из картинки не сразу ясно, какой вершине мы делаем splay, а в тексте этого явно не написано.
{{tick|ticked=1}} А сделай Zig, Zig-Zig и Zig-Zag подпунктами Splay, тогда нормально смотреться будет. --[[Участник:Dgerasimov|Дмитрий Герасимов]] 22:49, 8 апреля 2012 (GST)
{{tick|ticked=1}}Ну в общем-то я ничего против википедии не имею, картинки там вроде адекватные.
{{tick | ticked=1}} Почему ничего нет про Find? Обязательно надо написать, что он тоже меняет дерево.
{{tick}} еще пару слов сказать про сплей-деревья по неявному ключу.