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