Транзитивне замикання

• Якщо ${\displaystyle X}$ — це множина людей (живих або мертвих), і ${\displaystyle R}$ — відношення «є батьком або матір'ю», тоді транзитивним замиканням ${\displaystyle R}$ є відношення «є предком». Якщо ${\displaystyle X}$ — це множина аеропортів, а ${\displaystyle xRy}$ еквівалентне «існує рейс від ${\displaystyle x}$ до ${\displaystyle y}$», і транзитивне замикання ${\displaystyle R}$ дорівнює ${\displaystyle P}$, тоді ${\displaystyle xPy}$ еквівалентне «можливо долетіти з ${\displaystyle x}$ до ${\displaystyle y}$ літаком» (хоча, можливо, з пересадками).

A = {Болт, Гайка, Двигун, Автомобіль, Колесо, Вісь}

причому деякі з деталей і конструкцій можуть використовуватися при складанні інших конструкцій. Взаємозв'язок деталей описується відношенням R («безпосередньо використовується в») і складається з наступних кортежів:

Таблиця 1. Відношення R.
Транзитивне замикання складається з кортежів (додані кортежі позначені жирним):

Таблиця 2. Транзитивне замикання відношення R.

Очевидний сенс замикання R полягає в описі включення деталей не тільки безпосередньо одне в одного, а й через використання їх у проміжних деталях, наприклад, болт використовується в автомобілі, так як він використовується в двигуні, а двигун використовується в автомобілі.

(Теорія)

Граф зі шістьма вершинами та сімома ребрами

Нехай ${\displaystyle G(V,E)}$ – орієнтований граф, ${\displaystyle A}$ – його матриця суміжності.

Означення. Шляхом з вершини ${\displaystyle v_{1}}$ до вершини ${\displaystyle v_{k}}$ у графі ${\displaystyle G}$ називається послідовність ребер ${\displaystyle (v_{1},v_{2}),(v_{2},v_{3}),(v_{3},v_{4}),...,(v_{k-1},v_{k})}$, кожне з яких належить ${\displaystyle E}$. Довжиною шляху називається кількість задіяних в ньому ребер. Шлях називається простим, якщо в ньому жодна вершина не проходиться двічі (за винятком можливо першої та останньої вершини). Циклом називається простий шлях, який починається та закінчується в одній і тій же вершині. Граф,що не містить циклів, називається ациклічним.

Означення. Булева матриця ${\displaystyle C}$, в якій ${\displaystyle C[i,j]=1}$ тоді і тільки тоді коли існує шлях з вершини і до вершини ${\displaystyle j}$, називається транзитивним замиканням матриці суміжності ${\displaystyle A}$.

Транзитивне замикання можна обчислити за допомогою алгоритму Флойда, застосувавши на ${\displaystyle k}$-тій ітерації наступну формулу до булевої матриці ${\displaystyle C:}$

${\displaystyle C_{k}[i,j]=C_{k-1}[i,j]orC_{k-1}[i,k]andC_{k-1}[k,j])}$

Ця формула встановлює існування шляху від ${\displaystyle i}$ до ${\displaystyle j}$, який проходить через вершини з номерами не більшими за ${\displaystyle k}$, лише в наступних випадках:

• Вже існує шлях від ${\displaystyle i}$ до ${\displaystyle j}$, який проходить через вершини з номерами не більшими за ${\displaystyle _{k-1}}$.
• Існує шлях від ${\displaystyle i}$ до ${\displaystyle _{k}}$, який проходить через вершини з номерами не більшими за ${\displaystyle _{k-1}}$ та шлях від ${\displaystyle _{k}}$ до ${\displaystyle j}$, який також проходить через вершини з номерами не більшими за ${\displaystyle _{k-1}}$.

Алгоритм обчислення транзитивного замикання ще до Флойда розробив Уоршелл, тому наведений далі алгоритм називається алгоритмом Уоршелла.

     procedure Warshall;
         begin
            var i, j, k: integer;
               for k = 1 to n
                for i = 1 to n
                  for j = 1 to n
                    W[i][j] = W[i][j] or (W[i][k] and W[k][j])
         end;

Приклад. Запустимо алгоритм Уоршелла на графі, поданому на рисунку 1. Матриця суміжності A та матриця транзитивного замикання C мають вид:

${\displaystyle A=}$${\displaystyle {\begin{bmatrix}0&1&0&0&0&0\\0&0&0&0&0&0\\1&0&0&0&1&0\\0&1&0&0&0&0\\0&0&0&0&0&1\\0&0&0&1&0&0\\\end{bmatrix}}}$ ${\displaystyle ,C=}$ ${\displaystyle {\begin{bmatrix}0&1&0&0&0&0\\0&0&0&0&0&0\\1&1&0&1&1&1\\0&1&0&0&0&0\\0&1&0&1&0&1\\0&1&0&1&0&0\\\end{bmatrix}}}$

Розглянемо матрицю суміжності ${\displaystyle A}$ графу ${\displaystyle G}$ як булеву матрицю, в якій ${\displaystyle A[i,j]=1}$ якщо існує ребро, яке сполучає вершини ${\displaystyle i}$ та ${\displaystyle j}$ , та ${\displaystyle A{[i,j]}=0}$ інакше. Вважаємо, що довжини усіх ребер дорівнюють 1. Матриця суміжності містить інформацію про шляхи довжини 1 між вершинами графу. Матриця ${\displaystyle A}$ * ${\displaystyle A}$ = ${\displaystyle A^{2}}$ містить інформацію про наявність шляхів довжини 2. І взагалі, ${\displaystyle A^{n}[i,j]=1}$ якщо існує шлях між вершинами ${\displaystyle i}$ та ${\displaystyle j}$ довжини ${\displaystyle n}$. Якщо такого шляху не існує, то ${\displaystyle A^{n}{[i,j]}=0}$. Транзитивне замикання матриці суміжності ${\displaystyle A=}$ визначається як логічна операція or матриць ${\displaystyle A^{i}}$, ${\displaystyle i=1}$,${\displaystyle n}$, де ${\displaystyle n}$ – розмір матриці ${\displaystyle A}$ :

Closure${\displaystyle (A)}$  = ${\displaystyle A^{1}orA^{2}orA^{3}or...orA^{n}}$. 

Матриці суміжності ${\displaystyle A}$ та транзитивного замикання ${\displaystyle C}$ із прикладу пов’язані рівністю: ${\displaystyle C=A^{1}orA^{2}orA^{3}orA^{4}orA^{5}orA^{6}}$

• Транзитивне відношення
• Замикання (математика)
• Транзитивне скорочення

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)
• Куратовский К., Мостовский А. Теория множеств. — Москва : Мир, 1970. — 416 с.(рос.)
• Ван дер Варден Б. Л. Алгебра. — Москва : Наука, 1975. — 623 с. — ISBN 5-8114-0552-9.(рос.)
• Андерсон Джеймс Дискретна математика і комбінаторика = Discrete Mathematics with Combinatorics - М .: "Вільямс", 2006. - С. 960. - ISBN 0-13-086998-8.
• Бєлоусов А. І., Ткачов С. Б. Дискретна математика. Серія: Математика в технічному університеті. Вид-во: МГТУ ім. Н. Е. Баумана, 2001 .- 744 с. ISBN 5-7038-1769-2, 5-7038-1270-4
• Віленкін Н. Я. Комбінаторика - М ., 1969.
• Єрусалимський Я. М. Дискретна математика - djvu.504.com1.ru: 8019/WWW/6be408e8a605874170890817e8abb173.djvu - М ., 2000.
• Іванов Б. Н. Дискретна математика. Алгоритми і програми. Розширений курс - bnivanov.ru / book / Discrete_mathematics_BN_Ivanov.pdf - М .: Известия, 2011. - С. 512. - ISBN 978-5-206-00824-1.
• Іванов Б. Н. Дискретна математика. Алгоритми і програми. Видавництво: Физматлит, 2007. - 408 с. ISBN 978-5-9221-0787-7
• Капітонова Ю. В., Кривий С. Л., Летичівський А. А., Луцький Г. М. Лекції з дискретної математики - СПб. : БХВ-Петербург, 2004. - С. 624. - ISBN 5-94157-546-7.
• Кемени Дж., Снелл Дж., Томпсон Дж. Введення в кінцеву математику - М ., 1963. - С. 486.
• Новиков Ф. А. Дискретна математика для програмістів - 2-е вид. - СПб. : "Пітер", 2005. - С. 364. - ISBN 5-94723-741-5.
• Редькін М. П. Дискретна математика. Видавництво: Лань, 2006. - 96 с. ISBN 5-8114-0522-7
• Романовський І. В. Дискретний аналіз - 4-е изд. - СПб. : Невський Діалект; БХВ-Петербург, 2008. - С. 336.
• Яблонський С. В. Введення в дискретну математику - topology.math.csu.ru / library / posob / diskret / Yablonskij_Vvedenie_diskret.djvu - М .: Наука, 1979. - С. 272.