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

Question

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

Пусть 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, это либо t-> v1-> v2-> t, либо t-> v2-> v3-> t.Но не в состоянии доказать это.

Спасибо

Answer 1

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

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

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

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

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

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

Answer 2

Основная идея состоит в том, что самый короткий цикл имеет длину 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]), чей цикл по крайней мере на одну более короткую(есть только два направления на выбор: от т или до т).Повторите с более коротким циклом, пока не достигнете длины 3.

Answer 3

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

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

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

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

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

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

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