Редактирование: Транзитивное замыкание

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 15: Строка 15:
 
* <tex>R \subset R^+</tex> по определению <tex>R^+</tex>
 
* <tex>R \subset R^+</tex> по определению <tex>R^+</tex>
 
* <tex>R^+</tex> транзитивно. Пусть <tex>a R^+ b</tex> и <tex>b R^+ c</tex>. Это значит, что существуют <tex> i, j </tex> такие, что <tex>a R^i b</tex> и <tex>b R^j c</tex>. Но тогда <tex>a R^{i+j} c</tex>, и, так как <tex>R^{i+j} \subset R^+</tex>, то <tex>a R^+ c</tex>
 
* <tex>R^+</tex> транзитивно. Пусть <tex>a R^+ b</tex> и <tex>b R^+ c</tex>. Это значит, что существуют <tex> i, j </tex> такие, что <tex>a R^i b</tex> и <tex>b R^j c</tex>. Но тогда <tex>a R^{i+j} c</tex>, и, так как <tex>R^{i+j} \subset R^+</tex>, то <tex>a R^+ c</tex>
* <tex>R^+</tex> {{---}} минимальное отношение, удовлетворяющее представленным требованиям. Пусть <tex>T</tex> {{---}} транзитивное отношение, содержащее <tex>R</tex> в качестве подмножества. Покажем, что <tex>R^+ \subset T</tex>. <tex>R \subset T \Leftrightarrow R^i \subset T</tex> для любого натурального <tex>i</tex>. Докажем это по индукции. <tex>R^1 = R \subset R^+</tex>, как было показано выше. Пусть верно для любого <tex>i \leqslant k</tex>. Пусть <tex>a R^{k+1} c</tex>. Но тогда существует <tex>b: aR^kb</tex> и <tex>bRc</tex>, но <tex>R \subset T, R^k \subset T</tex>, следовательно <tex>aTb, bTc</tex>. Из транзитивности <tex>T</tex> следует, что <tex>aTc</tex>, следовательно <tex>R^{k+1} \subset T</tex>.
+
* <tex>R^+</tex> {{---}} минимальное отношение, удовлетворяющее представленным требованиям. Пусть <tex>T</tex> {{---}} транзитивное отношение, содержащее <tex>R</tex> в качестве подмножества. Покажем, что <tex>R^+ \subset T</tex>. <tex>R \subset T \Leftrightarrow R^i \subset T</tex> для любого натурального <tex>i</tex>. Докажем это по индукции. <tex>R^1 = R \subset R^+</tex>, как было показано выше. Пусть верно для любого <tex>i \le k</tex>. Пусть <tex>a R^{k+1} c</tex>. Но тогда существует <tex>b: aR^kb</tex> и <tex>bRc</tex>, но <tex>R \subset T, R^k \subset T</tex>, следовательно <tex>aTb, bTc</tex>. Из транзитивности <tex>T</tex> следует, что <tex>aTc</tex>, следовательно <tex>R^{k+1} \subset T</tex>.
 
}}
 
}}
  
 
== Построение транзитивного замыкания ==
 
== Построение транзитивного замыкания ==
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <tex>R</tex> как отношение <tex>T</tex> такое, что <tex>aTb</tex> тогда и только тогда, когда существуют <tex>x_1, x_2, \ldots, x_n</tex> такие, что <tex>aRx_1, x_1Rx_2, x_2Rx_3, \ldots, x_{n-1}Rx_n, x_nRb</tex>, то есть существует путь из вершины <tex>a</tex> в вершину <tex>b</tex> по рёбрам графа отношения.
+
Представленное доказательство указывает на способ построения транзитивного замыкания, а также позволяет определить транзитивное замыкание отношения <tex>R</tex> как отношение <tex>T</tex> такое, что <tex>aTb</tex> тогда и только тогда, когда существуют <tex>x_1, x_2, \ldots, x_n</tex> такие, что <tex>aRx_1</tex>, <tex>x_1Rx_2</tex>, <tex>x_2Rx_3</tex>, \ldots, <tex>x_{n-1}Rx_n</tex>, <tex>x_nRb</tex>, то есть существует путь из вершины <tex>a</tex> в вершину <tex>b</tex> по рёбрам графа отношения.
  
 
{{Теорема
 
{{Теорема

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: