Transitive reduction of a digraph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Transitive reduction of a digraph''' --- транзитивная редукция орграфа. A ''' transitive reduction''' <math>TR</math> of a digraph <m…»)
 
(нет различий)

Текущая версия от 14:03, 4 августа 2011

Transitive reduction of a digraph --- транзитивная редукция орграфа.

A transitive reduction [math]\displaystyle{ TR }[/math] of a digraph [math]\displaystyle{ G = (V,A) }[/math] is a digraph [math]\displaystyle{ G^{-} = (V,A^{-}) }[/math] having the minimum number of arcs and the same transitive closure of [math]\displaystyle{ G }[/math]. It is known that, for any dag [math]\displaystyle{ G }[/math], the transitive reduction [math]\displaystyle{ G^{-} }[/math] is unique and is a subgraph (partial graph) of [math]\displaystyle{ G }[/math].