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

На вході маємо граф, а на виході його транзитивне замикання.

Транзитивне замикання бінарного відношення $R$ на множині $X$ — це найменше транзитивне відношення на множині $X$, що включає $R$.

«Найменше транзитивне відношення» визначається за допомогою відношення включення.

Це можливо, позаяк відношення само є множиною (а саме підмножиною декартового квадрата множини $X$). тому, якщо R₁ ⊂ R₂, тоді R₁ вважатимемо меншим за R₂.

Приклади

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

Приклад

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

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

Конструкція	Де використовується
Болт	Двигун
Болт	Колесо
Гайка	Двигун
Гайка	Колесо
Двигун	Автомобіль
Колесо	Автомобіль
Вісь	Колесо

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

Конструкція	Де використовується
Болт	Двигун
Болт	Колесо
Гайка	Двигун
Гайка	Колесо
Двигун	Автомобіль
Колесо	Автомобіль
Вісь	Колесо
Болт	Автомобіль
Гайка	Автомобіль
Вісь	Автомобіль

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

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

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

(Теорія)

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

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

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

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

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

$C_k[i, j] = C_{k-1}[i, j] or C_{k-1}[i, k] and C_{k-1}[k, j])$

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

• Вже існує шлях від $i$ до $j$, який проходить через вершини з номерами не більшими за $_{k-1}$.
• Існує шлях від $i$ до $_k$, який проходить через вершини з номерами не більшими за $_{k-1}$ та шлях від $_k$ до $j$, який також проходить через вершини з номерами не більшими за $_{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 мають вид:

$A=$$\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}$ $,C=$ $\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}$

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

Closure$(A)$  = $A^1 or
A^2 or A^3 or ... or A^n$. 

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

Дивись також

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

Джерела

• Куратовский К., Мостовский А. (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.