Транзитивный остов - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:39:36Z

rollbackEdits.php mass rollback

217.79.179.7 в 03:43, 1 сентября 2022

2022-09-01T03:43:20Z

Gaporf: /* Доказательство корректности */ Если отношение ТОЛЬКО антисимметрично, то граф может иметь цикл

2018-09-10T18:54:31Z

‎Доказательство корректности: Если отношение ТОЛЬКО антисимметрично, то граф может иметь цикл

188.242.29.236 в 10:15, 3 января 2018

2018-01-03T10:15:43Z

188.242.29.236 в 12:08, 28 декабря 2017

2017-12-28T12:08:24Z

188.242.29.236 в 13:39, 27 декабря 2017

2017-12-27T13:39:35Z

Alexandra: /* Псевдокод */

2017-01-08T23:01:10Z

‎Псевдокод

Alexandra: /* Алгоритм для антисимметричных отношений */

2017-01-08T22:54:48Z

‎Алгоритм для антисимметричных отношений

Alexandra: /* Описание алгоритма */

2017-01-08T22:25:54Z

‎Описание алгоритма

Alexandra в 22:15, 8 января 2017

2017-01-08T22:15:41Z

← Предыдущая		Версия 16:39, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=		\|definition=

← Предыдущая		Версия 03:43, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=		\|definition=

@@ Строка 33: / Строка 33: @@
 '''Транзитивным замыканием''' (англ. ''transitive closure'') графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V \mid i \underset{G}{\leadsto} j \right \} </tex>.
 }}
-Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
+Так как отношение антисимметрично и транзитивно, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.
 Докажем теорему, из которой следует алгоритм.
@@ Строка 53: / Строка 53: @@
 Так как множества <tex> E^- </tex> и <tex> \left \{  k \underset{G}{\to} m \mid  \forall l: [ k \underset{G}{\leadsto} l \wedge l \underset{G}{\to} m \Longrightarrow k = l ] \right \} </tex> включены друг в друга, они совпадают, то есть равны.
 }}
 ===Ассимптотика===
 Для множества <tex>X</tex> c количеством элементов <tex>n</tex> алгоритм работает за <tex>O(n^3)</tex>, так как в каждом из трёх циклов мы пробегаемся по всем элементам множества <tex>X</tex>.

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

@@ Строка 1: / Строка 1: @@
 {{Определение
 |definition=
-'''Транзитивным остовом''' (англ. ''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] (англ. ''transitive closure'') <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
+'''Транзитивным остовом''' (англ. ''transitive reduction'') [[Определение отношения|отношения]] <tex> R </tex> на множестве <tex> X </tex> называется минимальное отношение <tex> R^- </tex> на <tex> X </tex> такое, что [[транзитивное замыкание]] <tex> R^- </tex> равно транзитивному замыканию <tex> R </tex>.
 }}
@@ Строка 31: / Строка 31: @@
 {{Определение
 |definition=
-'''Транзитивным замыканием''' графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V \mid i \underset{G}{\leadsto} j \right \} </tex>.
+'''Транзитивным замыканием''' (англ. ''transitive closure'') графа <tex> G = \left < V, E \right > </tex> называется граф <tex> G^* = \left < V, E^* \right > </tex>, где <tex> E^* = \left \{ (i, j) \in V \times V \mid i \underset{G}{\leadsto} j \right \} </tex>.
 }}
 Так как отношение антисимметрично, то граф ацикличен, то есть в нём выполняется следующее: <tex> \forall i, j \in V: i \underset{G}{\overset{+}{\leadsto}} j \Longrightarrow i \neq j </tex>.

@@ Строка 18: / Строка 18: @@
          '''foreach''' <tex>c \in X</tex>
            '''if''' <tex>aRb</tex> '''and''' <tex>bRc</tex> '''and''' <tex>aRc</tex>
-             <tex>R^-\setminus(a, c)</tex>
+             <tex>R^- = R^-\setminus(a, c)</tex>
 ===Доказательство корректности===

@@ Строка 7: / Строка 7: @@
 == Алгоритм для антисимметричных отношений ==
 ===Описание алгоритма===
-Чтобы найти минимальное отношение <tex>R^-</tex> на <tex>X</tex> такое, что транзитивное замыкание <tex>R^-</tex> равно транзитивному замыканию <tex>R</tex>, рассмотрим всевозможные комбинации из каждых трёх элементов <tex>a, b, c \in X</tex>. И если для этих элементов существуют отношения <tex>aRb</tex>, <tex>bRc</tex> и <tex>aRc</tex>, то избавимся от отношения <tex>aRc</tex>. После проверки всех комбинаций получаем отношение <tex>R^-</tex>.
+Пусть первоначально <tex>R^-=R</tex>.
 === Псевдокод ===
    '''function''' <tex>f</tex>(<tex>X</tex>: '''List<T>''', <tex>R</tex>: '''List<T>'''):