Транзитивно ориентируемый граф

Материал из WEGA
Перейти к навигации Перейти к поиску

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

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

Литература

[WG'93]