有向S—回路和有向S—迹

本文给出了有向生成回路和有向生成迹的几个充分条件。 设G为强连通1—图,无环,n阶。对于G的任两不相邻顶点x,y。①如果 d(x)+d(y)≥2n+1。那么对于G的任两顶点u和v,或有u-v有向S-迹,或有v-u有向S-迹。②如果 d(x)+d(y)≥2n-3。那么G含有向S-回路。