Предварительное условие для графов с уникальной топологической сортировкой

Question

Предположим, что рассматриваемый граф является DAG (ориентированный ациклический граф).

Вопрос : могу ли я заключить, что такой граф будет иметь уникальную топологическую сортировку, если и только если только одна из его вершин не имеет входящих ребер?

Другими словами, нужна ли только одна вершина без входящих ребер (но не достаточно) для генерации уникальной топологической сортировки?

Answer 1

Топологическая сортировка будет уникальной в том и только в том случае, если между каждой парой последовательных вершин в топологическом порядке имеется направленное ребро (т. Е. У орграфа есть гамильтонов путь ). Источник

Гамильтонов путь означает, что путь между двумя вершинами будет посещать каждую вершину только один раз, но это не значит, что у одной вершины не должно быть входящих ребер.У вас может быть гамильтонов путь, который на самом деле представляет собой цикл .Это все равно будет генерировать уникальный топологический вид (конечно, это будет цикл, если это важно для вас).

Надеюсь, это поможет

Answer 2

Хааааа, ок.извините за недоразумение.

В этом случае я предполагаю, что вы правы, вот набросок доказательства:

У нас есть уникальный топологий sot => У нас есть только одна вершина, которой она являетсяЛегально ставить на первое место => Для каждой вершины, кроме одной, не легально ставить на первое место => Для каждой вершины, кроме одной, у нас есть ребра сжимания.

Надеюсь, что теперь яответил на ваш вопрос ....

Answer 3

Нет! Граф ниже имеет только одну вершину без входящих ребер и имеет 2 возможных решения.

1 -> 2
3 -> 4
3 -> 1
4 -> 2

Два решения:

2 0 3 1
2 3 0 1

Answer 4

Кто-то дал ответ.Здесь я просто хочу привести контрпример: G = {(1,2), (1,3)}.В этом случае существует 2 допустимых топологических вида: 1,2,3 и 1,3,2

Answer 5

Да, вы можете сказать, что в качестве необходимого условия, как если бы было несколько узлов с ин-градусом = 0, тогда не будет гамильтонова траектории, следовательно, нет уникального топологического порядка.Только для начального узла графов (в степени = 0) не будет входящего ребра, остальные вершины ДОЛЖНЫ иметь входящее ребро от своего топологического предка, то есть узел непосредственно перед текущим узлом в топологическом порядке.Если у каждого последовательного узла в топологическом порядке нет ребра, DAG НЕ будет иметь уникальный порядок.