图的循环定向

Barot,Geiss和Zelevingsky曾经给出了一个图是否可定向的判断方法.该方法对图中所有圈上的边依次排序编号,然后考察不同的圈是否有不同的极大边,或者是计算顶点、边、圈和连通分支间的数量关系.本文给出另外一种判定方法.该方法主要通过观察顶点之间的链进行.

Cyclical orientations of graphs

Barot, Geiss and Zelevinsky gave a method to decide whether a given graph can be cyclically oriented. Their method is either to consider the linear order of the edges such that different chordless cycles have different maximal edges, or to check the number relation among the amount of vertices, edges, cycles and connected components. In this paper, another method is proposed to decide whether a given graph can be cyclically oriented. The method is to use the chains between two vertices.