探索Euler图的等价命题

doi:10.3969/j.issn.1000-5641.2018.02.003

华东师范大学学报(自然科学版) ›› 2018, Vol. 2018 ›› Issue (2): 23-30,40.doi: 10.3969/j.issn.1000-5641.2018.02.003

探索Euler图的等价命题

孙慧¹, 姚兵^1,2

1. 西北师范大学数学与统计学院, 兰州 730070;
2. 兰州交通大学电子与信息工程学院, 兰州 730070

收稿日期:2017-02-20 出版日期:2018-03-25 发布日期:2018-03-22
通讯作者: 姚兵,男,教授,研究方向为图着色与标号、复杂网络及优化.E-mail:yybb918@163.com. E-mail:yybb918@163.com
作者简介:孙慧,女,硕士研究生,研究方向为图着色与标号、复杂网络.E-mail:18919104606@163.com.
基金资助:
国家自然科学基金（61163054，61363060，61662066）

Exploring equivalent definitions of eulerian graphs

SUN Hui¹, YAO Bing^1,2

1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China;
2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

Received:2017-02-20 Online:2018-03-25 Published:2018-03-22

摘要/Abstract

摘要： 从研究Euler图的等价命题入手，尝试挖掘Euler图的拓扑结构，力图从多个角度刻画Euler图的本征，得到4个新的Euler图等价命题，并利用图的"浓缩"和"稀释"运算给出刻画Euler图的技术，且此技术能够转化为可行的算法.

关键词: Euler图, 无邻顶点重合运算, 边收缩运算, 顶点剖分运算, 2-度拆分运算

Abstract: From the topic of equivalent propositions of eulerian graph to start our study, we try to dig the topology of eulerian graph, and to describe eulerian graph from the view of different insights. Finally, we obtain four new equivalent propositions of eulerian graph by the technique of "concentration" and "dilution" operations, which can be transformed into two feasible algorithms.

Key words: eulerian graph, non-adjacent identifying operation, edge contraction operation, vertex subdivision operation, 2-degree split operation

中图分类号:

O157.5

孙慧, 姚兵. 探索Euler图的等价命题[J]. 华东师范大学学报(自然科学版), 2018, 2018(2): 23-30,40.

SUN Hui, YAO Bing. Exploring equivalent definitions of eulerian graphs[J]. Journal of East China Normal University(Natural Sc, 2018, 2018(2): 23-30,40.

参考文献

[1] BONDY A J, MURTY U S R. Graph Theory with Applications[M]. London:The MaCmillan Press Ltd, 1976.
[2] 石怡, 王旭培. 欧拉图的最大特征值[J]. 湖州师范学院学报, 2008, 30(2):13-15.
[3] 侯远, 陈育栎, 郑艺容, 等. 欧拉图的hyper-Wiener指标[J]. 高校应用数学学报, 2016, 31(2):248-252.
[4] CHEN Z H. Snarks, hypohamiltonian graphs and non-supereulerian graphs[J]. Graphs and Combinatorics, 2016, 32(6):2267-2273.
[5] 李赤松, 李战春, 江敏. 基于欧拉图的授权扩散拓扑构建与授权撤销[J]. 小型微型计算机系统, 2012, 33(10):2208-2212.
[6] 游松发, 赵红艳. 欧拉图与Capelli多项式[J]. 湖北大学学报(自然科学版), 2011, 33(4):444-447.
[7] 赵红艳. 欧拉图与矩阵环的多项式恒等式[D]. 武汉:湖北大学, 2013.
[8] 唐海宏. 欧拉图在逻辑教学中的运用[J]. 林区教学,, 2012(10):4-5.
[9] SUO X, ZHU Y, OWEN G S. Graphical passwords:A survey[C]//Computer Security Applications Conference. DBLP, 2005:463-472.
[10] FLEISCHNER H. 欧拉图与相关专题[M]. 孙志人, 李皓, 刘桂珍, 等, 译. 北京:科学出版社, 2012.
[11] 陈慧敏. 在C_k(l, m)中的k-超欧拉图[D]. 武汉:华中师范大学, 2015.
[12] 安明强, 熊黎明. 超欧拉图、可折叠图及匹配[J]. 应用数学学报, 2016, 39(6):871-877.
[13] WANG B. A degree-sum condition for edge-supereulerian graphs[J]. Journal of Southwest China Normal University, 2009, 34(1):16-19.
[14] 李登信, 王斌, 李宵民. 关于判定超欧拉图的收缩法[J]. 重庆工商大学学报(自然科学版), 2003, 20(1):1-4.
[15] 李霄民. 判定超欧拉图的一个新方法[J]. 西南大学学报(自然科学版), 2007, 29(4):41-43.
[16] 苏静, 马飞, 姚兵. 2-连通图的一些等价定义[J]. 东北师大学报(自然科学版), 2017, 49(1):33-37.
[17] 苏静, 马飞, 姚兵. 探索2-边连通图的等价定义[J]. 华东师范大学学报(自然科学版), 2017(1):19-25.
[18] 王晓敏, 赵喜杨, 姚兵. 关于树的若干等价性命题[J]. 陕西师范大学学报(自然科学版), 2016, 44(2):11-14.

探索Euler图的等价命题

Exploring equivalent definitions of eulerian graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	韩鑫胤, 姚敏, 左连翠, 周伟娜. 几类图的字典式乘积图的(d,1)-全标号[J]. 华东师范大学学报(自然科学版), 2019, 2019(3): 35-41.
[2]	章溢, 刘志强, 邹思思, 温利民. 基于分层贝叶斯模型的损失准备金估计[J]. 华东师范大学学报(自然科学版), 2019, 2019(1): 13-23.
[3]	陈晓峰, 王艺桥. 最大度为7的哈林图的L(2,1)-标号[J]. 华东师范大学学报(自然科学版), 2019, 2019(1): 39-47,57.
[4]	师雪芹, 唐霞, 韦玉梅, 王健. 安徽省细鳞苔科植物物种多样性调查与研究[J]. 华东师范大学学报(自然科学版), 2018, 2018(4): 138-146.
[5]	张全锐, 刘建成. 欧氏空间中超曲面的L²调和2-形式[J]. 华东师范大学学报(自然科学版), 2018, 2018(3): 38-45.
[6]	苏亚攀, 潘海林, 赵振杰, 袁萌平. 磁偶极作用对铁基纳米晶条带LDGMI效应的影响[J]. 华东师范大学学报(自然科学版), 2018, 2018(3): 129-135,156.
[7]	陈少军, 李晓涛, 郑军华. 蛋白酶体激活因子REGγ的肿瘤相关靶蛋白研究进展[J]. 华东师范大学学报(自然科学版), 2018, 2018(2): 125-130,159.
[8]	周枭潇, 毕春娟, 汪萌, 周雅, 陈振楼. 大气沉降对叶菜重金属的污染效应及其健康风险[J]. 华东师范大学学报(自然科学版), 2018, 2018(2): 141-150.
[9]	李艺春, 孙慧, 姚兵. 几种可扩散网络模型的边魔幻偶优美性[J]. 华东师范大学学报(自然科学版), 2018, 2018(1): 11-16,23.
[10]	董勇鹏, 王茜茹, 马娇娇. 一般时间终端一致连续多维BSDE解的稳定性[J]. 华东师范大学学报(自然科学版), 2018, 2018(1): 24-34,49.
[11]	杨琰琰, 魏文龙, 黄志刚. 几类微分与差分方程组的亚纯解[J]. 华东师范大学学报(自然科学版), 2018, 2018(1): 50-58.
[12]	马飞, 姚兵. 基于两种不同择优概率下的无标度网络模型[J]. 华东师范大学学报(自然科学版), 2017, 2017(6): 42-49.
[13]	马骅, 蒋雪中. 长江口潮周期内总悬浮颗粒物浓度的光学反演算法分析[J]. 华东师范大学学报(自然科学版), 2016, 2016(3): 146-155.
[14]	许洋. 非负特征图的列表不完全染色的研究(英)[J]. 华东师范大学学报(自然科学版), 2016, 2016(2): 51-55.
[15]	何常香, 刘伟龙. 2n阶(n-2)-正则二部图的最小基本圈基[J]. 华东师范大学学报(自然科学版), 2016, 2016(2): 56-61.