Циклы в ориентированном графе

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

Пусть v1, v2, v3 ... vn и t - n + 1 вершина в ориентированном графе. v1, v2, v3 ... vn образуют ориентированный ациклический граф. t подключен к каждому из v1, v2, v3 ... vn. Теперь, поскольку v1, v2, v3 ... v4 связаны ациклическим образом, если есть цикл, то он будет включать t. Можем ли мы показать, что все циклы длины больше 3 всегда будут включать цикл длины 3. помните, что t связано с каждым v1, v2 ... vn, и парных циклов нет.

Объясняя проблему дальше.

Скажем, ациклический ориентированный граф вершин v1, v2, v3..vn равен v1-> v2-> v3 -> ... vn. У каждого v есть ребро к t. Скажем, есть цикл t-> v1-> v2-> v3-> t. Такой цикл наверняка включает цикл длины 3 i.t либо t-> v1-> v2-> t, либо t-> v2-> v3-> t. Но я не могу это доказать.

Спасибо


graph algorithm graph-algorithm
person Lipika Deka    schedule 01.09.2011    source источник
comment
t- ›v1-› v2- ›2 должно быть t-› v1- ›v2-› t?   -  person Muthu Ganapathy Nathan    schedule 01.09.2011
comment
Связано ли t с vn через направленное ребро - в одном направлении - или в обоих направлениях? В первом случае я считаю ваш вывод неверным. В последнем случае доказательство тривиально; однако, возможно, в этом случае также существует цикл длины 2 между t и каждым другим узлом.   -  person davmac    schedule 01.09.2011
comment
@davmac .... t подключен к vn через одно направление ... мой вывод может быть неверным и, следовательно, я хотел увидеть его через доказательство. Не могли бы вы привести пример некорректности. Благодарность   -  person Lipika Deka    schedule 01.09.2011
comment
@Juggler, на самом деле я думаю, что вывод правильный, доказательства ниже.   -  person davmac    schedule 01.09.2011

Ответы (3)


arrow_upward
5
arrow_downward

ПОЛЬЗОВАТЬСЯ МЕТОДОМ ПОДТВЕРЖДЕНИЯ СЛУЧАЯМИ:

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

Рассмотрим Граф G с вершинами v1, v2, v3 ... vn. И пусть График G будет ациклическим ориентированным графом.

page1page2

Если k = 0, очевидно, что t-> vi-> vj-> t имеет подцикл длины 3.

Следовательно, доказано.

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

person Muthu Ganapathy Nathan    schedule 01.09.2011
comment
+1 потому что ты меня опередил ... и мне нужно любить рукописные заметки. - person davmac; 01.09.2011
comment
Серьезно, люблю рукописные заметки ... Большое спасибо ... вернусь после того, как изучу доказательство - person Lipika Deka; 01.09.2011
comment
@Juggler Iam только в переполнении стека. Если вам нужно обоснование по какой-либо части доказательства, спросите себя сейчас. - person Muthu Ganapathy Nathan; 01.09.2011
comment
@Juggler Многие не решались спросить: это ваше задание или в какой ситуации вы столкнулись с этой концепцией. На самом деле это хорошая концепция - person Muthu Ganapathy Nathan; 01.09.2011
comment
@ Eager_student .. Нет, это не задание. Проблема возникла из-за проблемы сериализации транзакций, над которой я работал. Большое спасибо за вашу помощь еще раз - person Lipika Deka; 01.09.2011

arrow_upward
5
arrow_downward

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

Итак, цикл имеет не менее t и две другие вершины.

Любой путь между двумя вершинами, образующий цикл с t, имеет длину 3 или более.

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

Представьте себе путь между v [a] и v [b] как отрезок колеса, а соединения вершин v [i] на пути к t как спицы ... вы всегда можете найти более короткий отрезок между v [ a] и v [b].

[ДОПОЛНЕНИЕ К НАПРАВЛЯЕМОМУ ГРАФИКУ]
Пусть v [a] происходит от t, а v [b] идет к t, а v [a] ведет к v [b]. Если цикл между v [a] и v [b] имеет длину 3, утверждение верно. В противном случае должна быть либо одна вершина после v [a], идущая в t (но не v [b]), либо вершина перед v [b], исходящая из t (но не v [a]), цикл которой как минимум на один короче (есть только два направления на выбор: от t или до t). Повторите с более коротким циклом, пока не достигнете длины 3.

person Arc    schedule 01.09.2011
comment
@Archimedix ... Вы правы, но как мне это официально показать. кроме того, мой граф - ориентированный граф. Спасибо - person Lipika Deka; 01.09.2011
comment
Я добавил некоторую информацию для доказательства по индукции, должно быть не слишком сложно формализовать это оттуда (кстати, я предполагаю, что это какое-то задание, поэтому, возможно, вам стоит попробовать выполнить эту часть :-)). - person Arc; 01.09.2011
comment
Ваше решение правильное. Выбрал другой из-за усилий, и он / она кажется студентом. Надеюсь, все в порядке. - person Lipika Deka; 01.09.2011
comment
Конечно, в конце концов, это ваш вопрос, поэтому вы выбираете тот ответ, который вам больше всего подходит. - person Arc; 01.09.2011

arrow_upward
2
arrow_downward

Простое доказательство:

  1. Предположим, что t является частью цикла, который включает в себя va и vb, а также другие узлы, где есть ребро t -> va и vb -> t

  2. тогда есть последовательность узлов [vc, vd, ve ...] в цикле между va и vb;

  3. Берем первый узел в наборе - vc. Существует либо ребро от t до vc, либо от vc до t (как вы заявили);

4а. если ребро от t до vc, то существует более короткий цикл, чем цикл с [t, va, vb], потому что мы можем перейти от t непосредственно к vc, минуя va; кроме того, если этот новый цикл имеет длину больше 3, этот процесс может быть повторен в новом цикле, начиная с шага 1.

4b. В противном случае ребро будет от vc до t, и есть цикл длины 3 - t до va, от va до vc, от vc до t.

Следовательно, любой цикл можно сократить до длины 3.

person davmac    schedule 01.09.2011
comment
Именно это я и пытался доставить. Но я объяснил на двух страницах с множеством диаграмм, а вы сделали то же самое в одном абзаце. + 1 для краткого и приятного объяснения. - person Muthu Ganapathy Nathan; 01.09.2011