Всегда ли сортировка с удалением источника возвращает максимальный цикл?

Я написал алгоритм удаления источника для сортировки некоторых зависимостей между таблицами в нашей базе данных, и оказалось, что у нас есть цикл. Для простоты предположим, что у нас есть таблицы A, B, C и D. Ребра выглядят следующим образом:

(A, B)
(B, A)
(B, C)
(C, D)
(D, A)

Как видите, здесь два цикла. Один находится между A и B, а другой - между всеми четырьмя из них. Будет ли этот тип сортировки всегда подавляться на самом большом цикле? Или это не обязательно так?


dependencies graph-theory topological-sort
person Jason Baker    schedule 02.04.2010    source источник
comment
Понятия не имею, о чем вы говорите. Но если у вас был алгоритм с полиномиальным временем, который всегда давал вам самый длинный цикл, вы доказали, что P = NP. кстати, вы имели в виду самый длинный / максимальный вместо максимального?   -  person    schedule 03.04.2010
comment
@Moron - возможно. Я подумал, что они имели в виду то же самое. :-)   -  person Jason Baker    schedule 09.04.2010

Ответы (2)


arrow_upward
5
arrow_downward

Под удалением источника я полагаю, вы имеете в виду на каждом этапе удаление узла без входящих ребер.

Я думаю, вы просите найти максимальный эйлеров тур по вашему графу (т.е. цикл с уникальными ребрами, в то время как узлы могут повторяться).

Очевидно, что ни одна вершина в цикле не может быть удалена (ни одна вершина в цикле не будет иметь нулевых входящих ребер), поэтому этот алгоритм определенно сохраняет все циклы (и самый большой), но все же он не поможет вам найти < / em>, оставшиеся ребра не гарантированно входят в какой-либо цикл (я легко могу построить пример, в котором описываемый вами алгоритм сохраняет все ребра, в то время как самые большие цикл просто имеет размер два, поэтому не очень помогает в поиске последнего).

Вот как вы можете это сделать:

Вас интересует распознавание задних ребер, т. Е. В обходе ребра, которое указывает на предка (в дереве DFS, которое создается ребрами посещающих узлов в первый раз) посещенный узел. Например, если в стеке DFS есть узлы [A-> B-> C-> D] и пока вы исследуете D, вы обнаруживаете край D-> B, это задний край. Каждый задний край определяет цикл.

Что еще более важно, циклы, индуцированные задними ребрами, являются базовым набором циклов графа. «Базовый набор циклов»: вы можете построить все циклы графа, просто объединив и XORing циклы базового набора. Например, рассмотрим циклы [A1-> A2-> A3-> A1] и [A2-> B1-> B2-> B3-> A2]. Вы можете объединить их в цикл: [A1-> A2-> B1-> B2-> B3-> A2-> A3-> A1]. Поскольку вам нужен максимальный цикл, вам не нужно рассматривать XOR.

  • Постройте максимальный цикл, объединив все базовые циклы, которые пересекаются в узле. (Если вы сделаете это осторожно, это также должно иметь линейную временную сложность).

С другой стороны, если вам требуется максимальный цикл без повторяющейся вершины, это будет намного сложнее линейного :)

person Dimitris Andreou    schedule 06.04.2010
comment
На самом деле я не пытаюсь найти тот или иной тип цикла. На самом деле я бы предпочел не иметь циклов (удаление исходного кода действительно требует DAG). Однако я заметил такое поведение в программе, которую я написал, и мне было просто любопытно, следует ли всегда ожидать такого поведения. - person Jason Baker; 09.04.2010

arrow_upward
0
arrow_downward

Ваш алгоритм удаления исходного кода (который, как я предполагаю, означает удаление узлов без зависимостей по одному, как Dimitris) будет подавляться в любом цикле. Фактически, алгоритм удалит все узлы, которые не зависят от циклов, а оставшиеся узлы будут либо частью цикла, либо зависеть от узла, который является частью цикла.

Эти циклы также называются сильно связанными компонентами, и если вы замените каждый цикл одним узлом, вы бы есть DAG.

person MSN    schedule 11.11.2010