Кіріспе
Бинарлық қатынасты қамтитын ең кіші транзитивті қатынас – бинарлық қатынастың транзитивті жабылуы. Математикада, Х жиынындағы R гомогенді бинарлық қатынастың транзитивті жабылуы – Х жиынында R қатынасын қамтитын және транзитивті болатын ең кіші қатынас. Шекті жиындар үшін "ең кіші" сөзі әдеттегі мағынасында, яғни ең аз байланысты жұптарға ие болу ретінде қарастырылады; шексіз жиындар үшін ол R-дің бірегей ең кіші транзитивті супержиыны болып табылады.
the transitive closure of a binary relation
In mathematics, the transitive closure of a homogeneous binary relation R on a set X is the smallest relation on X that contains R and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets is the unique minimal transitive superset of R.
For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation such that means "it is possible to fly from x to y in one or more flights". More formally, the transitive closure of a binary relation R on a set X is the smallest (w. r. t. ⊆) transitive relation on X such that R ⊆ ; see We have = R if, and only if, R itself is transitive. Conversely, transitive reduction adduces a minimal relation S from a given relation R such that they have the same closure, that is, ; however, many different S with this property may exist. Both transitive closure and transitive reduction are also used in the closely related area of graph theory.
Мысалы, егер X әуежайлар жиыны болса және x R y дегеніміз "x әуежайынан y әуежайына тікелей рейстер бар" дегенді білдірсе (X-тегі x және y үшін), онда R-дің X-тегі транзитивті жабылуы – "x-тен y-ға бір немесе бірнеше рейстермен ұшуға болады" деген қатынас. Әлдеқайда ресми түрде айтқанда, бинарлық қатынас R-дің X жиынындағы транзитивті жабылуы – R ⊆ болатындай, X-тегі ең кіші (⊆ қатынасына қатысты) транзитивті қатынас. Егер R өзі транзитивті болса, онда = R болады. Керісінше, транзитивті қысқарту берілген R қатынасынан S минималды қатынасын шығарады, осылайша олардың жабылулары бірдей болады, яғни ; алайда, осы қасиетке ие көптеген түрлі S болуы мүмкін. Транзитивті жабу және транзитивті қысқарту графтар теориясының тікелей байланысты саласында да қолданылады.
the transitive closure of a binary relation
In mathematics, the transitive closure of a homogeneous binary relation R on a set X is the smallest relation on X that contains R and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets is the unique minimal transitive superset of R.
For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation such that means "it is possible to fly from x to y in one or more flights". More formally, the transitive closure of a binary relation R on a set X is the smallest (w. r. t. ⊆) transitive relation on X such that R ⊆ ; see We have = R if, and only if, R itself is transitive. Conversely, transitive reduction adduces a minimal relation S from a given relation R such that they have the same closure, that is, ; however, many different S with this property may exist. Both transitive closure and transitive reduction are also used in the closely related area of graph theory.
Транзитивті қатынастар және мысалдар
X жиынындағы R қатынасы транзитивті болады, егер X-тегі барлық x, y, z үшін, егер x R y және y R z болса, онда x R z. Транзитивті қатынастардың мысалдарына кез келген жиынтақтағы теңдік қатынасы, кез келген сызықтық реттелген жиынтақтағы "кіші немесе тең" қатынасы және барлық адамдар жиынтығындағы "x, y-дан бұрын туған" қатынасы жатады. Символдық түрде бұл былай белгіленеді: егер x < y және y < z болса, онда x < z. Транзитивті емес қатынастың бір мысалы – барлық қалалар жиынтығындағы "x қаласына y қаласынан тікелей рейстер арқылы жетуге болады". Бір қаладан екінші қалаға тікелей рейс болғанымен, екінші қаладан үшінші қалаға тікелей рейс болуы, бірінші қаладан үшінші қалаға тікелей рейс болатынын білдірмейді. Осы қатынастың транзитивті жабылуы – мүлдем басқа қатынас, атап айтқанда, "x қаласынан басталып y қаласында аяқталатын тікелей рейстер тізбегі бар". Кез келген қатынасты осыған ұқсас түрде транзитивті қатынасқа кеңейтуге болады. Аз мағыналы транзитивті жабылуы бар транзитивті емес қатынастың мысалы – "x, y апта күнінен кейінгі күні". Осы қатынастың транзитивті жабылуы – "күндердің бірінде x күнінен кейін y күні келеді", бұл аптаның барлық күндері үшін x және y үшін тривиальды түрде дұрыс (және осылайша Декарт квадратына тең, яғни "x және y – аптаның екі күні").
Қасиеттері
Екі транзитивті қатынастың қиылысуы транзитивті болады. Екі транзитивті қатынастың бірігуі міндетті түрде транзитивті болмайды. Транзитивтілікті сақтау үшін транзитивті жабуды қолдану қажет. Мысалы, екі эквиваленттік қатынасты немесе екі преордерді біріктіргенде мұндай жағдай туындайды. Жаңа эквиваленттік қатынас немесе преордер алу үшін транзитивті жабуды қолдану керек (эквиваленттік қатынастар үшін рефлексивтілік және симметрия автоматты түрде қамтамасыз етіледі).
Граф теориясында
Компьютерлік ғылымда транзитивті жабу тұжырымын деректер құрылымын құру ретінде қарастыруға болады, ол қолжетімділік сұрақтарына жауап беруге мүмкіндік береді. Яғни, a түйінінен d түйініне бір немесе бірнеше қадаммен жетуге бола ма? Бинарлық қатынас тек a түйінінің b түйінімен, ал b түйінінің c түйінімен байланысты екенін көрсетеді және т.с.с. Транзитивті жабылу құрылғаннан кейін, төмендегі суретте көрсетілгендей, O(1) операциясында a түйінінен d түйініне жетуге болатынын анықтауға болады. Деректер құрылымы әдетте бульдік матрица түрінде сақталады, сондықтан матрица[1][4] = true болса, 1 түйіні 4 түйініне бір немесе бірнеше қадаммен жете алады. Бағытталған ациклді графтың (DAG) жапсарлас қатынасының транзитивті жабылуы – DAG-тың қолжетімділік қатынасы және қатаң ішінара реттелуі. Бағытталмаған графтың транзитивті жабылуы кластерлік графты, кликалардың біріктірілмеген жиынтығын құрайды. Транзитивті жабылуды құру – графтың компоненттерін табу мәселесінің эквивалентті формулировкасы.
Деректер қорын сұрау тілдерінде
1980 жылдан бері Oracle Database декларативтік сұраныстың бір бөлігі ретінде транзитивті жабуды есептеуге мүмкіндік беретін CONNECT BY START WITH деген меншік SQL кеңейтімін енгізді. SQL 3 (1999) стандарты сұраныс өңдегішінде транзитивті жабылуларды есептеуге мүмкіндік беретін, көбірек мүмкіндіктерге ие РЕКУРСИВТІК ҚҰРЫЛЫМды қосты. 2011 жылдан бастап соңғысы IBM Db2, Microsoft SQL Server, Oracle, PostgreSQL және MySQL (v8.0+) жүйелерінде қолданысқа енгізілді. SQLite бұл мүмкіндікке қолдауды 2014 жылы ұсынды. Datalog та транзитивті жабылу есептеуін жүзеге асырады. MariaDB рекурсивті ортақ кестелік өрнектерді қолдайды, оларды транзитивті жабылуды есептеу үшін пайдалануға болады. Бұл мүмкіндік 2016 жылдың сәуір айында шыққан 10.2.2 нұсқасында енгізілді.
Алгоритмдер
Графтың іргелес қатынасының транзитивті жабылуын есептеуге арналған тиімді алгоритмдерді табуға болады. Мәселені іргелес матрицаларды көбейтуге келтіру ең төменгі уақыт күрделілігіне жетеді, атап айтқанда матрицалық көбейтудің күрделілігі (, ), 2020 жылғы мәліметтер бойынша. Дегенмен, бұл тәсіл практикалық емес, себебі тұрақты коэффициенттері де, сирек графтар үшін жадты пайдалану да жоғары. Мәселені Флойд-Уоршалл алгоритмімен немесе графтың әрбір түйінінен басталатын ендікке бірінші іздеу немесе тереңдікке бірінші іздеу арқылы да шешуге болады. Бағытталған графтар үшін Пурдом алгоритмі мәселені алдымен оның конденсациялық DAG және оның транзитивті жабылуын есептеу арқылы шешеді, содан кейін оны бастапқы графқа көтереді. Оның орындалу уақыты , мұндағы – оның күшті байланысқан компоненттері арасындағы қабырғалар саны. Соңғы зерттеулер MapReduce парадигмасына негізделген үлестірілген жүйелерде транзитивті жабылуды есептеудің тиімді жолдарын қарастырды.