Топ питань
Часова шкала
Чат
Перспективи

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

З Вікіпедії, вільної енциклопедії

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

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

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

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

Це можливо, позаяк відношення само є множиною (а саме підмножиною декартового квадрата множини ). Тому, якщо R1R2, тоді R1 вважатимемо меншим за R2.

Remove ads

Приклади

  • Якщо — це множина людей (живих або мертвих), і — відношення «є батьком або матір'ю», тоді транзитивним замиканням є відношення «є предком». Якщо — це множина аеропортів, а еквівалентне «існує рейс від до », і транзитивне замикання дорівнює , тоді еквівалентне «можливо долетіти з до літаком» (хоча, можливо, з пересадками).
Remove ads

Приклад

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

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

Більше інформації Конструкція, Де використовується ...

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

Більше інформації Конструкція, Де використовується ...

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

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

Remove ads

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

Узагальнити
Перспектива

(Теорія)

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

Нехай – орієнтований граф, – його матриця суміжності.

Означення. Шляхом з вершини до вершини у графі називається послідовність ребер , кожне з яких належить . Довжиною шляху називається кількість задіяних в ньому ребер. Шлях називається простим, якщо в ньому жодна вершина не проходиться двічі (за винятком можливо першої та останньої вершини). Циклом називається простий шлях, який починається та закінчується в одній і тій же вершині. Граф,що не містить циклів, називається ациклічним.

Означення. Булева матриця , в якій тоді і тільки тоді коли існує шлях з вершини і до вершини , називається транзитивним замиканням матриці суміжності .

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

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

  • Вже існує шлях від до , який проходить через вершини з номерами не більшими за .
  • Існує шлях від до , який проходить через вершини з номерами не більшими за та шлях від до , який також проходить через вершини з номерами не більшими за .

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

     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 мають вид:


Розглянемо матрицю суміжності графу як булеву матрицю, в якій якщо існує ребро, яке сполучає вершини та , та інакше. Вважаємо, що довжини усіх ребер дорівнюють 1. Матриця суміжності містить інформацію про шляхи довжини 1 між вершинами графу. Матриця * = містить інформацію про наявність шляхів довжини 2. І взагалі, якщо існує шлях між вершинами та довжини . Якщо такого шляху не існує, то . Транзитивне замикання матриці суміжності визначається як логічна операція or матриць , ,, де – розмір матриці  :

Closure  = . 

Матриці суміжності та транзитивного замикання із прикладу пов’язані рівністю:

Remove ads

Див. також

Джерела

  • Ван дер Варден Б. Л. Алгебра. — Москва : Наука, 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.
Remove ads
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads