1
Неориентированный граф имеет транзитивную ориентацию, если его ребра могут быть ориентированы таким образом, что если (x, y) и (y, z) являются двумя ребрами в результирующем ориентированном графе, также существует ребро (x, z) в результирующем ориентированном графе.Как проверить, существует ли транзитивная ориентация для заданного неориентированного графа?
Я работаю с веб-сетями реального питания, и мне нужно проверить, имеет ли непрозрачный неориентированный граф (который моделирует конкуренцию в пищевой сети) транзитивную ориентацию. Неориентированный граф представлен как матрица смежности в Java.
EDIT:
Например, for this undirected graph,
Мы можем ориентировать края в this way. Итак, этот график имеет транзитивную ориентацию.
Я ответил, но потом я заметил, что вы используете «неориентированный граф» и «направленный график» в обсуждении. Это опечатка или что? – nbro
После ориентации ребер неориентированного графа результирующий граф является ориентированным графом. –
Возможно, я что-то упустил. Поскольку вы определили «наличие TO», я считаю, что любой путь в исходном неориентированном графе должен лежать в полном подграфе. Следовательно, каждый связный компонент должен быть полным графом для исходного графа с TO. Это довольно легко проверить. Если я ошибаюсь, примеры неполных графиков, имеющих TO, были бы полезными. – Gene