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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Транзитивно ориентируемый граф''' (''Transitively orientable graph'') - граф, ребра которо...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Транзитивно ориентируемый граф''' (''Transitively orientable graph'') -
'''Транзитивно ориентируемый граф''' (''[[Transitively orientable graph]]'')
граф, ребра которого можно ориентировать так, что получившийся
[[граф]], [[ребро|ребра]] которого можно ориентировать так, что получившийся
орграф будет транзитивным. Граф, который допускает в точности две
[[орграф]] будет [[транзитивный орграф|транзитивным]]. Граф, который допускает в точности две
транзитивные ориентации, называется ''единственно транзитивно ориентируемым'' (uniquely transitively orientable graph).
транзитивные ориентации, называется ''[[единственно транзитивно ориентируемый граф|единственно транзитивно ориентируемым]]'' ([[uniquely transitively orientable graph]]).


Другое название --- ''Граф сравнимости''.
Другое название ''[[Граф сравнимости]]''.
==Литература==
==Литература==
[WG'93]
* Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.

Текущая версия от 18:06, 21 сентября 2011

Транзитивно ориентируемый граф (Transitively orientable graph) — граф, ребра которого можно ориентировать так, что получившийся орграф будет транзитивным. Граф, который допускает в точности две транзитивные ориентации, называется единственно транзитивно ориентируемым (uniquely transitively orientable graph).

Другое название — Граф сравнимости.

Литература

  • Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.