Transitiv sammentrækning

I matematik er den transitive reduktion af en binær relation R på en mængde X den minimale relation på X , således at den transitive lukning falder sammen med den transitive lukning af R. Hvis den transitive lukning af R er antisymmetrisk og endelig , så er den unik. Imidlertid er hverken eksistens eller unikhed garanteret i det generelle tilfælde. $R'$ $R'$ $R'$

Eksempel

I grafteori kan enhver binær relation R på X forstås som en rettet graf ( V , A ), hvor V = X er hjørnerne og A = R er buerne i grafen. Den transitive reduktion af en graf kaldes undertiden en minimal repræsentation . De følgende figurer repræsenterer en ikke-transitiv relation (venstre) og dens transitive kontraktion (højre).

Den transitive kontraktion af en endelig rettet acyklisk graf er unik.

Transitive reduktionsalgoritmer

Den transitive reduktion af en relation uden cyklusser kan findes ved hjælp af dens transitive lukning : $R^-$ $R$ $R^+$

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

Her betyder relationssammensætning . $\cirk$

Aho, Garey og Ullman (1972), som opfandt begrebet "transitiv kontraktion" i den her beskrevne betydning, etablerede også en forbindelse mellem transitiv lukning og kontraktion:

for at definere en transitiv kontraktion udvidede de opdagelsen af en transitiv lukning ved at behandle loops;
de viste, hvordan man opnår en transitiv lukning fra en transitiv kontraktion;
de viste, at det at finde en transitiv reduktion og en lukning har samme beregningsmæssige kompleksitet .

Tred -værktøjet i Graphviz [1] udfører transitiv grafreduktion ved hjælp af dybde-først-søgning .

Udvidelig datastruktur

Et af de mest velundersøgte problemer inden for beregningsgrafteori er lagringen af en konsistent historie med transitive lukninger af grafer, når hjørner og buer indsættes eller fjernes. I 1987 beskrev JA La Poutré og Jan van Leeuwen i deres ofte citerede værk Maintenance Of Transitive Closures And Transitive Reductions Of Graphs , en historielagringsalgoritme til både lukning og til reduktion af grafen. [2]

Algoritmen bruger

O(|E ny ||V|)

tid til sekventiel indsættelse af buer og

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

for sekventiel sletning, hvor E gammel er sættet af buer før indsættelse eller sletning og E ny efter. For grafer, hvor der ikke er nogen cyklusser, kræver sletning kun

O(|E gammel ||V|)

tid.

Se også

Transitivitet

Noter

A. Aho, M. Garey, J. Ullman. Den transitive reduktion af en rettet graf // SIAM Journal on Computing : journal. - 1972. - Juni ( bind 1 , nr. 2 ). - S. 131-137 . - doi : 10.1137/0201008 .