不含回路的有向圖一定存在拓撲排序？

首先，拓撲排序是指對于一個有向無環圖G，將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若<u，v> ∈E(G)，則u在線性序列中出現在v之前。那么，假設存在回路，v1,v2,v3,……,vn，v1，則邊<v1,v2>∈E(G)，故v1在v2之前，類似地，v2在v3之前，……，因此，得出，v1在vn之前。

又因為<vn,v1>∈E(G)，即vn在v1之前。相互矛盾，所以假設不成立。所以，一個圖能夠進行拓撲排序的一個必要條件就是圖中不存在環。