Как найти или показать существование цикла в ориентированном графе быстрее, чем за O(IVI+IEI)?

Question

[pavlik 322]

Как найти или хотя бы показать существование цикла в ациклическом ориентированном графе за быстрее, чем за O(IVI+IEI)? То есть мне даже не обязательно, чтобы были найдены эти рёбра приводящие к циклу

Comments

[Lynn «Кофеман»]

Как можно «найти цикл в ациклическом графе»?

[Wataru]

цикла в ациклическом ориентированном графе

. Вообще, в ациклическом графе циклов нет по определению. "ациклический" же, т.е. без циклов. Это опечатка же? Вы имели ввиду просто ориентированный граф?

[pavlik 322]

Wataru, Lynn «Кофеман», Да, опечатка, я имел в виду, что точно, что цикл всего один

[Wataru]

pavlik 322, Вы имели ввиду "не более один"? Если цикл один, то он точно есть.

[pavlik 322]

Wataru, Да…:-|

Answer 1

[Wataru]

Никак.

Это можно доказать. Вам так или иначе придется посмотреть на все ребра. Допустим, есть алгоритм, который всегда может проверить цикл, смотря не все ребра. Рассморим какой-то граф без циклов. Алгоритм там какие-то ребра посмотрел и сказал, что циклов нет. А мы возьмем и скормим этому алгоритму почти такой же граф, только одно из ребер, которые он вообще не трогал, сделаем обратным какому-то другому ребру в графе, сделав таким образом цикл. Но алгоритм посмотрит на те же самые ребра, увидет все то же самое и сделает точно такой же вывод, что циклов нет, и ошибется. Все потому что мы допустили алгоритм, который всегда смотрит не все ребра. Значит таких алгоритмов нет и там всегда будет хотя бы O(|E|).

Comments

[pavlik 322]

Ну по идее O(|E|) уже будет лучше

[Wataru]

pavlik 322, Только для очень частного случая разряженных графов. В худшем случае O(|E|) не быстрее O(|V|+|E|) и все то же O(|V|^2).