探索Euler图的等价命题

孙慧; 姚兵

doi:10.3969/j.issn.1000-5641.2018.02.003

探索Euler图的等价命题

doi: 10.3969/j.issn.1000-5641.2018.02.003

孙慧^1,,
姚兵^1,2, ,

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

基金项目:

国家自然科学基金 61163054

国家自然科学基金 61363060

国家自然科学基金 61662066

详细信息

作者简介:
孙慧, 女, 硕士研究生, 研究方向为图着色与标号、复杂网络.E-mail:18919104606@163.com

通讯作者:
姚兵, 男, 教授, 研究方向为图着色与标号、复杂网络及优化.E-mail:yybb918@163.com

中图分类号: O157.5
计量
- 文章访问数: 191
- HTML全文浏览量: 76
- PDF下载量: 376
- 被引次数: 0
出版历程
- 收稿日期: 2017-02-20
- 刊出日期: 2018-03-25

Exploring equivalent definitions of eulerian graphs

SUN Hui^1
,,
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

摘要

摘要: 从研究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.
- eulerian graph /
- non-adjacent identifying operation /
- edge contraction operation /
- vertex subdivision operation /
- 2-degree split operation

HTML全文

图 1 三种运算

Fig. 1 Three operations

下载: 全尺寸图片幻灯片

图 2 对$C_{10}$实施无邻顶点重合运算得到$K_5$的过程

Fig. 2 A process of obtaining $K_5$ by implementing some non-adjacent identifying operations to $C_{10}$

下载: 全尺寸图片幻灯片

图 3 对$K_7$实施一系列$2$-边连通$2$-度剖分运算得到$C_{21}$的过程

Fig. 3 A process from $K_7$ to $C_{21}$ by using a series of 2-edge-connected and 2-degree split operations

下载: 全尺寸图片幻灯片

参考文献(18)

[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. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hzhx200802003&dbname=CJFD&dbcode=CJFQ
[3]	侯远, 陈育栎, 郑艺容, 等.欧拉图的hyper-Wiener指标[J].高校应用数学学报, 2016, 31(2):248-252. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=gxyz201602014&dbname=CJFD&dbcode=CJFQ
[4]	CHEN Z H. Snarks, hypohamiltonian graphs and non-supereulerian graphs[J]. Graphs and Combinatorics, 2016, 32(6):2267-2273. doi: 10.1007/s00373-016-1718-7
[5]	李赤松, 李战春, 江敏.基于欧拉图的授权扩散拓扑构建与授权撤销[J].小型微型计算机系统, 2012, 33(10):2208-2212. doi: 10.3969/j.issn.1000-1220.2012.10.017
[6]	游松发, 赵红艳.欧拉图与Capelli多项式[J].湖北大学学报(自然科学版), 2011, 33(4):444-447. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hdzk201104011&dbname=CJFD&dbcode=CJFQ
[7]	赵红艳. 欧拉图与矩阵环的多项式恒等式[D]. 武汉: 湖北大学, 2013. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=sxjz200304005&dbname=CJFD&dbcode=CJFQ
[8]	唐海宏.欧拉图在逻辑教学中的运用[J].林区教学, , 2012(10):4-5. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=lqxj201210001&dbname=CJFD&dbcode=CJFQ
[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. http://cdmd.cnki.com.cn/Article/CDMD-10511-1015444195.htm
[12]	安明强, 熊黎明.超欧拉图、可折叠图及匹配[J].应用数学学报, 2016, 39(6):871-877. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=yysu201606007&dbname=CJFD&dbcode=CJFQ
[13]	WANG B. A degree-sum condition for edge-supereulerian graphs[J]. Journal of Southwest China Normal University, 2009, 34(1):16-19. http://en.cnki.com.cn/Article_en/CJFDTOTAL-XNZK200901004.htm
[14]	李登信, 王斌, 李宵民.关于判定超欧拉图的收缩法[J].重庆工商大学学报(自然科学版), 2003, 20(1):1-4. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=yzzk200301001&dbname=CJFD&dbcode=CJFQ
[15]	李霄民.判定超欧拉图的一个新方法[J].西南大学学报(自然科学版), 2007, 29(4):41-43. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=xnnd200704009&dbname=CJFD&dbcode=CJFQ
[16]	苏静, 马飞, 姚兵. 2-连通图的一些等价定义[J].东北师大学报(自然科学版), 2017, 49(1):33-37. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=dbsz201701008&dbname=CJFD&dbcode=CJFQ
[17]	苏静, 马飞, 姚兵.探索2-边连通图的等价定义[J].华东师范大学学报(自然科学版), 2017(1):19-25. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=hdsz201701004&dbname=CJFD&dbcode=CJFQ
[18]	王晓敏, 赵喜杨, 姚兵.关于树的若干等价性命题[J].陕西师范大学学报(自然科学版), 2016, 44(2):11-14. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=sxsz201602004&dbname=CJFD&dbcode=CJFQ