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

Транзитивне замикання бінарного відношення $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$ тоді і тільки тоді коли існує шлях з вершини і до вершини $j$, називається транзитивним замиканням матриці суміжності $A$.

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

$C_{k}[i,j]=C_{k-1}[i,j]orC_{k-1}[i,k]andC_{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}orA^{2}orA^{3}or...orA^{n}$. 

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

Див. також

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

Джерела

• Хаусдорф Ф. Теория множеств. — Москва ; Ленинград : ОНТИ, 1937. — 304 с. — ISBN 978-5-382-00127-2.(рос.)

• Куратовский К., Мостовский А. Теория множеств = Set Theory (Teoria mnogości). — М. : Мир, 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.