Транзитивное замыкание — различия между версиями
м (→Существование и описание) |
м (→Построение транзитивного замыкания) |
||
Строка 19: | Строка 19: | ||
Действительно, если по рёбрам графа есть путь длины <math>l > n</math>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <math>n</math> можно "выкинуть" из объединения. | Действительно, если по рёбрам графа есть путь длины <math>l > n</math>, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем <math>n</math> можно "выкинуть" из объединения. | ||
− | Для построения транзитивного отношения множества, заданного матрицей смежности, используется алгоритм Флойда | + | Для построения транзитивного отношения множества, заданного матрицей смежности, используется [[алгоритм Флойда — Уоршелла]]. |
== Свойства транзитивного замыкания == | == Свойства транзитивного замыкания == |
Версия 03:56, 4 октября 2010
Транзитивным замыканием
отношения на множестве называется пересечение всех транзитивных отношений, содержащих как подмножество (иначе, минимальное транзитивное отношение, содержащее как подмножество). Например, если - множество городов, и на них задано отношение , означающее, что если , то "существует автобусный маршрут из x в y", то транзитивным замыканием этого отношения будет отношение "существует возможность добраться из x в y, передвигаясь на автобусах".Содержание
Существование и описание
Транзитивное замыкание существует для любого отношения. Для этого отметим, что пересечение любого множества транзитивных отношений транзитивно. Более того, обязательно существует транзитивное отношение, содержащее
как подмножество (например, ).Докажем, что
является транзитивным замыканием отношения .- по определению
- транзитивно. Пусть и . Это значит, что существуют i, j такие, что и . Но тогда , и, так как , то
- - минимальное отношение, удовлетворяющее представленным требованиям. Пусть - транзитивное отношение, содержащее в качестве подмножества. Покажем, что . для любого натурального . Докажем это по индукции. , как было показано выше. Пусть верно для любого . Пусть . Но тогда существует и , но , следовательно . Из транзитивности следует, что , следовательно , что и требовалось доказать
Построение транзитивного замыкания
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения
как отношение такое, что тогда и только тогда, когда существуют такие, что , , , ..., , , то есть существует путь из вершины в вершину по рёбрам графа отношения.Из этого определения можно легко понять, если
- отношение на конечном множестве размера n, то транзитивным замыканием такого отношения будет отношение- .
Действительно, если по рёбрам графа есть путь длины
, то он проходит по всем вершинам графа, а, значит, в этом пути есть цикл и его можно отбросить, тем самым уменьшив длину пути. Длину пути можно уменьшать до того, как она не будет превосходить количество вершин графа (элементов множества), а значит, все пути длины более, чем можно "выкинуть" из объединения.Для построения транзитивного отношения множества, заданного матрицей смежности, используется алгоритм Флойда — Уоршелла.
Свойства транзитивного замыкания
- Транзитивное замыкание рефлексивного отношения рефлексивно, так как транзитивное отношение содержит исходное отношение
- Транзитивное замыкание симметричного отношения симметрично. Действительно, пусть , значит существуют такие, что . Но из симметричности отношения следует , а, следовательно,
- Транзитивное замыкание не сохраняет антисимметричность, например, для отношения на множестве
- Транзитивное замыкание транзитивного отношения - оно само
Рефлексивно-транзитивное замыкание
Отношение
, гдеиногда называют рефлексивно-транзитивным замыканием, хотя часто под "транзитивным замыканием" подразумевается именно
. Обычно различия между этими отношениями не являются значительными.