Tranzitivní kontrakce

V matematice je tranzitivní redukce binární relace R na množině X minimální relace na X tak, že tranzitivní uzávěr se shoduje s tranzitivním uzávěrem R. Pokud je tranzitivní uzávěr R antisymetrický a konečný , pak je jedinečný. V obecném případě však není zaručena ani existence, ani jedinečnost.

Příklad

V teorii grafů lze jakoukoli binární relaci R na X chápat jako orientovaný graf ( V , A ), kde V = X  jsou vrcholy a A = R  jsou oblouky grafu. Tranzitivní redukce grafu se někdy nazývá minimální reprezentace . Následující obrázky představují netranzitivní relaci (vlevo) a její tranzitivní kontrakci (vpravo).

Tranzitivní kontrakce konečného orientovaného acyklického grafu je jedinečná.

Transitivní redukční algoritmy

Tranzitivní redukci vztahu bez cyklů lze nalézt pomocí jeho tranzitivního uzavření :

Zde znamená vztahová kompozice .

Aho, Garey a Ullman (1972), kteří zavedli termín „tranzitivní kontrakce“ ve smyslu zde popsaném, také vytvořili spojení mezi tranzitivním uzavřením a kontrakcí:

Nástroj tred v Graphviz [1] provádí redukci tranzitivního grafu pomocí vyhledávání do hloubky .

Rozšiřitelná datová struktura

Jedním z nejlépe prostudovaných problémů ve výpočetní teorii grafů je ukládání konzistentní historie přechodových uzávěrů grafu, když jsou vkládány nebo odstraňovány vrcholy a oblouky. V roce 1987 JA La Poutré a Jan van Leeuwen popsali ve své často citované práci Maintenance Of Transitive Closures And Transitive Reductions Of Graphs algoritmus ukládání historie jak pro uzavření, tak pro zmenšení grafu. [2]

Algoritmus používá

O(|E nové ||V|)

čas pro sekvenční vkládání oblouků a

O(|E staré ||V|+|E staré | 2 )

pro sekvenční mazání, kde E old  je sada oblouků před vložením nebo odstraněním a E new  po. U grafů, ve kterých nejsou žádné cykly, je smazání pouze nutné

O(|E staré ||V|)

čas.

Viz také

Odkazy

  1. ↑ AT&T Labs Research – Softwarové nástroje . Získáno 15. ledna 2013. Archivováno z originálu 28. ledna 2013.
  2. ↑ CiteSeerX – Údržba přechodných uzávěrů a přechodných redukcí grafů . Získáno 15. ledna 2013. Archivováno z originálu 28. ledna 2013.

Poznámky

Odkazy