作者：马冉；冯琪

作者单位：河南理工大学数学与信息科学学院中原工学院理学院

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

基金：国家自然科学基金资助项目(10971201)；

关键词：有向图;均衡方向;树;圈;欧拉图;

DOI：10.16186/j.cnki.1673-9787.2012.02.001

分类号：O157.5