想知道我們是否可以證明以下內容，或者是否已經證明哪裏可以找到證明。有向圖中的循環
設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-> v1-> v2-> v3-> t。這樣的循環似乎肯定涉及長度爲3的循環，或者t→v1→v2→t或者t→v2→v3→t。但是，一個不能夠證明這一點。
由於
讓我們用證明方法的案件：
（因爲它是很難輸入的符號，我掃描的手寫頁和我附上這裏供您參考。）
讓我們考慮一個圖G，頂點爲v1，v2，v3 ... vn。並讓圖G是無環向圖。
若k = 0， 很明顯的情況下T-> VI-> vj-> T具有長度3.
的子週期。因此證明。
希望幫助！
+1，因爲你打敗了我......並且愛上了手寫的筆記。 – davmac
認真地說，愛手寫筆記...非常感謝..我回來後，我學習證明 –
@Juggler Iam堆棧溢出只。如果您需要證明任何部分的證明，現在就問自己。 –
的基本思想是，最短的週期具有長度爲3，因爲（I假設）t被通過一個連接到任何其它頂點且只有一個邊緣，而另一個頂點不形成沒有噸週期。
所以一個循環至少有t個和另外兩個頂點。
與t形成一個循環的兩個頂點之間的任何路徑長度爲3或更大。
對於這樣一個週期，則可以查找既連接到t直接連接到彼此（鄰居）的路徑上的兩個頂點，因此它們形成與長度3.
一個週期想象V之間的路徑[a]和v [b]作爲輪的一部分，以及到t的路徑上的頂點v [i]的連接作爲輻條...總是可以找到v [a]和v [ b]。
[用於定向GRAPH ADDITION]
令v [A]來自T和V [B]去T和V [A]領先至V [B]。 如果v [a]和v [b]之間的循環長度爲3，則該語句成立。 否則，必須是後一個頂點v [α]將T（但不是V [B]），或v前一頂點並[b]從噸到來（但不是V並[a]），其週期是至少一種較短（只有兩個方向可供選擇：從t到t）。 重複使用週期短，直到到達長度3
@Archimedix ...你是對的，但我如何正式表明這一點。此外，我的圖是一個有向圖。謝謝 –
我已經通過歸納法添加了一些證明信息，應該不會太難以從那裏形式化（順便說一句，我猜這是一些任務，所以也許你應該嘗試做那部分:-)）。 – Archimedix
您的解決方案是正確的。選擇另一個是因爲努力，他/她似乎是一個學生。希望它可以。 –
簡單的證明：
假設t是一個循環，它包括VA和VB，和其他節點，其中存在邊緣噸的一部分 - > VA和VB - >噸
那麼在va和vb之間的循環中有一系列節點[vc，vd，ve ...];
取集合中的第一個節點 - 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.
這就是我試圖提供的。但是我用2頁的圖解釋了許多圖表，但是你在一個段落中做了同樣的事情，+ 1爲簡短而甜蜜的解釋。 –
@davmac ...謝謝。 –
T-> V1-> V2-> 2必須是T-> V1-> V2->噸？ –
是否通過有向邊 - 單向或兩個方向連接到vn？如果前者，我認爲你的結論是不正確的。如果是後者，證明是微不足道的;然而，在這種情況下，也可以說t和其他節點之間的長度爲2的週期。 – davmac
@davmac .... t通過單一方向連接到vn ...我的結論可能不正確，因此希望通過證明查看它。你能舉一個不正確的例子嗎？謝謝 –