Транзитивная редукция орграфа: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Транзитивная редукция орграфа''' (''Transitive reduction of a directed graph'') - для данного о...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Транзитивная редукция орграфа''' (''Transitive reduction of a directed graph'') -
'''Транзитивная редукция орграфа''' (''[[Transitive reduction of a digraph|Transitive reduction of a directed graph]]'')
для данного орграфа <math>G</math> орграф с наименьшим числом дуг, транзитивное
для данного [[орграф|орграфа]] <math>G</math> орграф с наименьшим числом [[дуга|дуг]], [[транзитивное замыкание орграфа|транзитивное замыкание]] которого совпадает (изоморфно) с транзитивным замыканием
замыкание которого совпадает (изоморфно) с транзитивным замыканием
исходного [[граф|графа]] <math>G</math>.
исходного графа <math>G</math>.
==Литература==
==Литература==
[Свами-Тхуласираман]
* Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.

Текущая версия от 13:01, 20 сентября 2011

Транзитивная редукция орграфа (Transitive reduction of a directed graph) — для данного орграфа [math]\displaystyle{ G }[/math] орграф с наименьшим числом дуг, транзитивное замыкание которого совпадает (изоморфно) с транзитивным замыканием исходного графа [math]\displaystyle{ G }[/math].

Литература

  • Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.