Транзитивный остов — различия между версиями
(Новая страница: «{{Определение |definition= '''Транзитивным остовом''' (''transitive reduction'') [[Определение отношения|отн...») |
|||
| Строка 3: | Строка 3: | ||
'''Транзитивным остовом''' (''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>. | ||
}} | }} | ||
| + | |||
| + | == Алгоритм == | ||
| + | Воспользуемся определениями транзитивного замыкания и [[Транзитивное отношение|транзитивного отношения]]. Изначально <tex> R' = R </tex>. Очевидно, что если для <tex> a, b, c \in X </tex> существуют <tex> aRb, bRc, aRc </tex>, то из <tex> R' </tex> нужно исключить <tex> \left < a, c \right > </tex>. | ||
| + | R' = R | ||
| + | for (each a in X) | ||
| + | for (each b in X) | ||
| + | for (each c in X) | ||
| + | if (aRb and bRc and aRc) | ||
| + | R'.delete(pair(a, c)) | ||
== Источники == | == Источники == | ||
* [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction] | * [http://en.wikipedia.org/wiki/Transitive_reduction Wikipedia: Transitive reduction] | ||
Версия 21:03, 10 апреля 2012
| Определение: |
| Транзитивным остовом (transitive reduction) отношения на множестве называется минимальное отношение на такое, что транзитивное замыкание равно транзитивному замыканию . |
Алгоритм
Воспользуемся определениями транзитивного замыкания и транзитивного отношения. Изначально . Очевидно, что если для существуют , то из нужно исключить .
R' = R
for (each a in X)
for (each b in X)
for (each c in X)
if (aRb and bRc and aRc)
R'.delete(pair(a, c))
