База дуг: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''База дуг''' (''[[Arc base]]'') -
'''База дуг''' (''[[Arc base]]'')
минимальное подмножество множества [[дуга|дуг]] [[орграф|орграфа]], которое сохраняет
минимальное подмножество множества [[дуга|дуг]] [[орграф|орграфа]], которое сохраняет
[[отношение достижимости]] в исходном орграфе; другими словами, это ---
[[отношение достижимости]] в исходном орграфе; другими словами, это
множество дуг в [[транзитивная редукция орграфа|транзитивной редукции орграфа]].
множество дуг в [[транзитивная редукция орграфа|транзитивной редукции орграфа]].
==Литература==
==Литература==
[Зыков/69]
* Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.

Текущая версия от 13:17, 13 ноября 2010

База дуг (Arc base) — минимальное подмножество множества дуг орграфа, которое сохраняет отношение достижимости в исходном орграфе; другими словами, это — множество дуг в транзитивной редукции орграфа.

Литература

  • Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.