Транзитивно затворење

Из Википедије, слободне енциклопедије
Disambig.svg
Уколико сте тражили транзитивно затворење скупа, погледајте чланак транзитивни скуп.

У математици, транзитивно затворење бинарне релације R на скупу X је најмања транзитивна релација на X која садржи R .

На пример, ако је X скуп аеродрома, а xRy значи „има директан лет са аеродрома x на аеродром y“, онда је транзитивно затворење од R релација „могуће је летети са аеродрома x на аеродром y, у једном или више летова“. Или, ако је X скуп људи (живих или мртвих) и R релација „је родитељ од“, онда је транзитивно затворење од R релација „x је предак од y“ .

Опис[уреди]

За сваку релацију R, увек постоји транзитивно затворење. Да би се ово увидело, треба имати у виду да је пресек сваке фамилије транзитивних релација и сам транзитиван. Штавише, постоји најмање једна транзитивна релација која садржи R, тривијална: X × X. Транзитивно затворење R је онда дато пресеком свих транзитивних релација које садрже R.

Транзитивно затворење R се може описати на следећи конкретнији начин. Дефинишимо релацију Т на X тако да xTy акко постоји коначан низ елемената (xi) таквих да x = x0 и

x0Rx1, x1Rx2, …, xn−1Rxn, и xnRy

Лако је проверити да је релација Т транзитивна и да садржи R. Даље, било која транзитивна релација која садржи R мора такође садржати и Т, па је Т транзитивно затворење од R.

Формална нотација: R^+ = \bigcup_{i=1,2,..} R^i

Доказ да је Т најмања транзитивна релација која садржи R[уреди]

Нека је А произвољан скуп елемената.

Претпоставка: GA транзитивна релација RAGA TAGA. Следи (a,b)GA(a,b)TA. Следи посебно (a,b)RA .

Сада, према дефиницији релације Т, знамо да n (a,b)R^nA. Затим, i ,i < n ei А. Дакле, постоји пут од a до b, то је: aRAe1RA...RAe(n-1)RAb.

Али, због транзитивности GA на RA, i, i < n (a,ei)GA, па је (a,e(n-1))GA (e(n-1),b)GA, па због транзитивности GA, добијамо (a,b)GA. Ово је контрадикција са (a,b)GA.

Због тога, (a,b)AA, (a,b)TA (a,b)GA. Ово значи да је TG, за било коју транзитивну G која садржи R. Дакле, Т је најмања транзитивна релација која садржи R.

Последица[уреди]

Ako je R транзитивна, онда R = T.

Примене[уреди]

Приметимо да унија две транзитивне релације не мора бити транзитивна. Зато, да би сачували транзитивност једна од њих мора бити транзитивно затворење. Ово се на пример дешава када се узима унија две релације еквиваленције или две релације поретка. Да би добили нову релацију еквиваленције или поретка једна мора бити транзитивно затворење (У случају релације еквиваленције рефлексивност и симетричност су аутоматски) .

Транзитивно затворење усмереног ацикличног графа (UAG) је релација досежности графа и строго делимични поредак.

Теорија графова[уреди]

У рачунарству, појам транзитивног затворења се може сматрати као конструисање структуре података која омогућава да се одговори на питања о достижности. Тј. да ли се из чвора а у чвор d може стићи у једном или више корака? Бинарна релација говори само да је чвор а повезан са чвором b, да је чвор b повезан са чвором c, итд. Након конструкције транзитивног затворења, одлучиво је да ли је чвор d достижан из чвора а. Та структура података најчешће се представља у виду квадратне матрице, па ако је матрица[1][4] = 1, значи да се из чвора 1 може стићи у чвор 4 у једном или више корака.

Однос са сложеношћу[уреди]

У теорији сложености израчунавања, класа сложености NL се подудара са скупом исказних формула које користе логику првог реда заједно са транзитивним затворењем. То је због тога што су својства транзитивног затворења у блиској вези са NL-комплетним проблемом STCON тј. проблемом проналажења директног пута у графу. Слично, класи L одговара логика првог реда са комутативним, транзитивним затворењем. Када је транзитивно затворење додато логици другог реда добија се класа PSPACE.

Блиски концепти[уреди]

Транзитивна редукција релације R је најмања релација која садржи транзитивно затворење од R као своје транзитивно затворење. Уопштено, она није јединствена.

Алгоритми[уреди]

Вероватно најједноставнији начин за то је Флојд–Варшалов алгоритам.

Литература[уреди]

  • Lidl, R. and Pilz, G., 1998, Applied abstract algebra, 2nd edition, Undergraduate Texts in Mathematics, Springer, ISBN 0-387-98290-6
  • Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog

Спољашње везе[уреди]