圆有向图中的泛弧

Universal arcs in round digraphs

设D=(V,A)是一个有向图,uv是D上的一条弧。如果对于任意顶点w∈V(D),都有弧uv和顶点w包含在某个公共圈中,则称弧uv是D的一条泛弧。证明了圆有向图R的每条弧都是泛弧当且仅当R是一个圈或者R是2-强连通的且R不属于一类特殊的圆有向图。并由此给出了判断圆有向图的每条弧是否都是泛弧的多项式算法。

An arc uv of a digraph D is called universal, if uv and w are in a common cycle for any vertex w of D. We prove that every exceptional class of 2-strong whether each arc of a round arc of a round digraph R is universal if and only if R is a cycle or R is an round digraphs. And we also give a polynomial algorithm to recognize digraph is universal