赋予图均衡方向的欧拉图构造法和圈树分解法

Two ways to give a gaph balanced orientation-Eulerian Construction and cyclek-Tree Construction

提出了2种赋予任意一个图均衡方向的方法:欧拉图构造法和圈树分解法,第一种方法是欧拉图构造法:若给定的图是欧拉图,先找到欧拉环游后再顺着欧拉环游的方向给边赋予方向,若不是欧拉图,可以通过给此非欧拉图补充边得到欧拉图赋予边方向后,再删除添加的边即可得到均衡有向图.第二种方法是圈树分解法,分两步进行:先假设图G是一棵树,运用树的特殊结构给出了赋予树G均衡方向的算法,因为森林是多棵树的并,所以若G是森林,此算法也能赋予G均衡方向.最后结合圈上每个顶点的度都是偶数,给出了总算法并证明了此算法能给任意一个图赋予均衡方向.

The paper focuses on the problem of turning an arbitrary graph into a balanced digraph by providing each edge orientation and presents two methods to give a graph balanced orientation, namely Eulerian Construc- tion and Cycle-Tree Construction. A balanced digraph is a digraph wheve │ d ＋ （v） - d- （v） │ ≤ 1 for each vertex of the digraph. The first method is Eulerian Construction based on the fact that a connected graph is an Eulerian graph if and only if it is even. The second method is to construct a cycle - tree decomposition by ap- plying the constructions of cycle and tree and give each edge orientation in G. Furthermore, the proof is pro- vided for the way to give an arbitrary graph balanced orientation.