방향 그래프의 순환

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 사이클이 있다고 가정 해보십시오. 이러한 사이클은 반드시 t-> v1-> v2-> t 또는 t-> v2-> v3-> t 중 하나 인 길이 3 i t의 사이클을 포함하는 것으로 보인다. 그러나 이것을 증명할 수는 없습니다.

감사

Answer 1

미국이 CASES에 의해 증명의 방법을 사용하자 :이 표기법을 입력하기 어렵 기 때문에는

(나는 필기를 스캔 페이지와 저는 참조 용으로 첨부합니다.)

그래프 G를 정점 v1, v2, v3 ... vn으로 가정 해 봅시다. 그리고 그래프 G를 비순환 적으로 향하게 한 그래프로 만들자.

K = 0, 것이 명백한 경우라면 그 T-> VI-> vj-> t 길이 3.

의 서브 사이클은 따라서 입증되었다.

희망 하시겠습니까?

Answer 2

기본적인 아이디어 t은 하나를 통해 다른 정점에 연결하고 하나의 가장자리에있다 (나는 가정), 다른 정점 t없이 사이클을 형성하지 않기 때문에 짧은주기의 길이가 3을 가지고 있다는 것입니다 .

그래서 사이클에는 적어도 t와 두 개의 다른 정점이 있습니다.

t와주기를 형성하는 두 정점 사이의 경로는 길이가 3 이상입니다.

이러한주기를 들어, 그러므로 그들이 V 사이의 경로를 상상해 길이 3.

와 사이클을 형성, T로 모두 연결되어 서로 직접 (이웃)에 연결된 경로에 두 정점을 찾을 수 있습니다 [a]와 v [b]를 바퀴의 한 부분으로하고, 꼭지점 v [i]를 쐐기 모양의 경로에 연결하면 ... v [a]와 v [ 비].

[감독 그래프 ADDITION]
하자 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.

Answer 3

간단한 증명 :

1. 가 t 가정은 에지 t가 VA와 VB 및 다른 노드를 포함하는주기의 일부 -> VA와 VB -> t

2. va와 vb 사이의주기에 노드 시퀀스 [vc, vd, ve ...]가있다.

3. set-vc의 첫 번째 노드를 가져옵니다. t에서 vc로 또는 vc에서 t로 가장자리가 있습니다 (명시한대로).

4a. 엣지가 t에서 vc이면, [t, va, vb]와 관련된주기보다 짧은주기가 있습니다. 왜냐하면 우리는 t에서 직접 vc로 건너 뛸 수 있기 때문입니다. 또한,이 새로운주기가 3보다 긴 경우,이 과정은 단계 1에서 시작하는 새로운주기에 대해 반복 될 수있다.

4b. 그렇지 않으면, 모서리는 vc에서 t까지이고, 길이 3 - t에서 va, va에서 vc, vc - t의주기가 있습니다.

따라서, 어떤주기는 3