Contracție tranzitivă

În matematică , reducerea tranzitivă a unei relații binare R pe o mulțime X este relația minimă pe X astfel încât închiderea tranzitivă coincide cu închiderea tranzitivă a lui R . Dacă închiderea tranzitivă a lui R este antisimetrică și finită , atunci este unică. Cu toate acestea, nici existența, nici unicitatea nu sunt garantate în cazul general. $R'$ $R'$ $R'$

Exemplu

În teoria grafurilor, orice relație binară R pe X poate fi înțeleasă ca un graf direcționat ( V , A ), unde V = X sunt vârfurile și A = R sunt arcele graficului. Reducerea tranzitivă a unui grafic este uneori numită reprezentare minimă . Următoarele figuri reprezintă o relație netranzitivă (stânga) și contracția sa tranzitivă (dreapta).

Contracția tranzitivă a unui graf aciclic direcționat finit este unică.

Algoritmi de reducere tranzitivă

Reducerea tranzitivă a unei relații fără cicluri poate fi găsită folosind închiderea sa tranzitivă : $R^-$ $R$ $R^+$

R^- = R - (R \circ R^+)

Aici înseamnă compoziția relației . $\circ$

Aho, Garey și Ullman (1972), care au inventat termenul „contracție tranzitivă” în sensul descris aici, au stabilit și o legătură între închiderea tranzitivă și contracție:

pentru a defini o contracție tranzitivă, au extins constatarea unei închideri tranzitive prin prelucrarea buclelor;
au arătat cum se obține o închidere tranzitivă dintr-o contracție tranzitivă;
au arătat că găsirea unei reduceri tranzitive și a unei închideri au aceeași complexitate de calcul .

Utilitarul tred din Graphviz [1] efectuează reducerea tranzitivă a graficului folosind căutarea depth-first .

Structură de date extensibilă

Una dintre cele mai bine studiate probleme în teoria grafurilor computaționale este stocarea unui istoric consistent al închiderilor tranzitive ale grafurilor atunci când vârfurile și arcele sunt inserate sau eliminate. În 1987, JA La Poutré și Jan van Leeuwen au descris, în lucrarea lor des citată, Maintenance Of Transitive Closures And Transitive Reductions Of Graphs , un algoritm de stocare a istoricului atât pentru închidere, cât și pentru reducerea graficului. [2]

Algoritmul folosește

O(|E nou ||V|)

timp pentru introducerea secvenţială a arcelor şi

O(|E vechi ||V|+|E vechi | 2 )

pentru ștergerea secvențială, unde E vechi este setul de arce înainte de inserare sau ștergere și E nou după. Pentru graficele în care nu există cicluri, ștergerea necesită doar

O(|E vechi ||V|)

timp.

Vezi și

Tranzitivitatea

Link -uri

↑ AT&T Labs Research - Instrumente software . Consultat la 15 ianuarie 2013. Arhivat din original pe 28 ianuarie 2013. (nedefinit)
↑ CiteSeerX - Întreținerea închiderilor tranzitive și reducerilor tranzitive ale graficelor . Consultat la 15 ianuarie 2013. Arhivat din original pe 28 ianuarie 2013. (nedefinit)

Note

A. Aho, M. Garey, J. Ullman. Reducerea tranzitivă a unui grafic direcționat // SIAM Journal on Computing : jurnal. - 1972. - Iunie ( vol. 1 , nr. 2 ). - P. 131-137 . - doi : 10.1137/0201008 .

Link -uri

Mathworld: Reducere tranzitivă
E.Reingold, Yu.Nivergelt, N.Deo ALGORITMI COMBINATORI. TEORIE ȘI PRACTICĂ M.: Mir, 1980, 476 pag.