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

• 作者: 冯琪 马冉
• 来源期刊: 河南理工大学学报：自然科学版
• 学科: 工学
• 关键词: 有向图 均衡方向 树 圈 欧拉图
• 年，卷（期）: 2012,（2）
• 所属期刊栏目: 基础学科
• 页码范围: 232-234
• 页数: 3页
• 分类号: TP18
• 字数: 2443字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-9787.2012.02.022

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	冯琪	中原工学院理学院	18	20	3.0	4.0
2	马冉	河南理工大学数学与信息科学学院	21	10	2.0	2.0