Transitiv kontraktion

I matematik är den transitiva reduktionen av en binär relation R på en mängd X den minimala relationen på X så att den transitiva slutningen sammanfaller med den transitiva slutningen av R . Om den transitiva stängningen av R är antisymmetrisk och finit , så är den unik. Men varken existens eller unikhet garanteras i det allmänna fallet. $R'$ $R'$ $R'$

Exempel

I grafteorin kan vilken binär relation R på X som helst förstås som en riktad graf ( V , A ), där V = X är hörn och A = R är bågarna i grafen. Den transitiva reduktionen av en graf kallas ibland en minimal representation . Följande figurer representerar en icke-transitiv relation (vänster) och dess transitiva sammandragning (höger).

Den transitiva sammandragningen av en finit riktad acyklisk graf är unik.

Transitiva reduktionsalgoritmer

Den transitiva reduktionen av en relation utan cykler kan hittas med dess transitiva stängning : $R^-$ $R$ $R^+$

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

Här betyder relationssammansättning . $\cirkel$

Aho, Garey och Ullman (1972), som myntade termen "transitiv kontraktion" i den mening som beskrivs här, etablerade också ett samband mellan transitiv stängning och kontraktion:

för att definiera en transitiv sammandragning utökade de upptäckten av en transitiv stängning med bearbetningscykler;
de visade hur man får en transitiv stängning från en transitiv sammandragning;
de visade att hitta en transitiv reduktion och en stängning har samma beräkningskomplexitet .

Tred- verktyget i Graphviz [1] utför transitiv grafreduktion med hjälp av djup-först-sökning .

Utökningsbar datastruktur

Ett av de mest välstuderade problemen inom beräkningsgrafteorin är lagringen av en konsekvent historia av transitiva stängningar av grafer när hörn och bågar sätts in eller tas bort. 1987 beskrev JA La Poutré och Jan van Leeuwen, i sitt ofta citerade verk Maintenance Of Transitive Closures And Transitive Reductions Of Graphs , en historiklagringsalgoritm för både stängning och för att reducera grafen. [2]

Algoritmen använder

O(|E ny ||V|)

tid för sekventiell infogning av bågar och

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

för sekventiell radering, där E gammal är uppsättningen av bågar före insättning eller radering och E ny efter. För grafer där det inte finns några cykler krävs endast radering

O(|E gammal ||V|)

tid.

Se även

Transitivitet

Länkar

↑ AT&T Labs Research - Programvaruverktyg . Hämtad 15 januari 2013. Arkiverad från originalet 28 januari 2013. (obestämd)
↑ CiteSeerX - Underhåll av transitiva stängningar och transitiva minskningar av grafer . Hämtad 15 januari 2013. Arkiverad från originalet 28 januari 2013. (obestämd)

Anteckningar

A. Aho, M. Garey, J. Ullman. Den transitiva reduktionen av en riktad graf // SIAM Journal on Computing : journal. - 1972. - Juni ( vol. 1 , nr 2 ). - S. 131-137 . - doi : 10.1137/0201008 .

Länkar

Mathworld: Transitiv reduktion
E.Reingold, Yu.Nivergelt, N.Deo KOMBINATORISKA ALGORITHMER. TEORI OCH PRAKSIS M.: Mir, 1980, 476 sidor.