探索2-边连通图的等价定义

基金项目:

国家自然科学基金 61163054, 61163037, 61363060

Probing equivalent definitions of 2-edge connected graphs

College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

摘要: k-边连通图在网络研究和图论研究中有着极其重要的地位.图论中有关2-,边连通图的命题很多, 它们刻画了2-,边连通的本质.本文给出17种关于2-边连通图的等价性命题,力图从不同角度深入理解、挖掘2-边连通图的本征,并从本文定义的2种新运算出发, 提出了新的有关2-边连通图的命题,并给出这些命题相互间的等价性证明.
- 2-边连通图 /
- 耳边分解 /
- 块 /
- 迹 /
- 圈
Abstract: As known, k-edge connected graphs play an important role in the research of networks and graph theory. There are many propositions of 2-edge connected graphs nowadays, which depict the essences of 2-edge connected graphs. We present 17 equivalent propositions of 2-edge connected graphs and dig more properties of 2-edge connected graphs from different aspects of 2-edge connected graphs. Furthermore, two equivalent propositions of 2-edge connected graphs by two new operations are proposed, and then we provide the equivalent proofs between the propositions we have collected and discovered.
- 2-edge connected graph /
- ear edge decomposition /
- block /
- trail /
- cycle

图 1 一条 (u,v)-链

Fig. 1 A (u,v)-chain

下载: 全尺寸图片幻灯片

图 2 (a)一个(x,U)-迹扇,粗线是 (x,v)-迹 P,蓝色线是 (x,u)-迹 Q;(b)一个特殊的 (x,U)-迹扇,(x,v)-迹必须通过顶点 u

Fig. 2 (a) An (x,U)-trail fan,where the (x,v)-trail P is in thick line,the (x,u)-trail Q is blue line; (b) An (x,U)-trail fan,but any (x,v)-trail must pass the vertex u

下载: 全尺寸图片幻灯片

图 3 (a)图G; (b)图H

Fig. 3 (a) Graph G; (b) Graph H

下载: 全尺寸图片幻灯片

图 4 一个反三角形边收缩的例子

Fig. 4 An example of the anti-triangle edge contraction

下载: 全尺寸图片幻灯片

[1]	CRUCITTI P, LATORA V, MARCHIORI M, et al. Error and attack tolerance of complex networks [J]. Physica A, 2004, 340: 388-394. doi: 10.1016/j.physa.2004.04.031
[2]	KRAPIVSKY P L, REDNER S, LEYVRAZ F. Connectivity of growing random networks [J]. Phys Rev Lett, 2000, 85(21): 4629-4632. doi: 10.1103/PhysRevLett.85.4629
[3]	YAO B, YANG C, YAO M, et al. Graphs as models of scale-free networks [J]. Applied Mechanics and Materials, 2013, 380-384: 2034-2037.
[4]	YAO B, WANG H Y, YAO M, et al. On the collapse of graphs related to scale-free networks [C]//Proceeding of the 3rd International Conference on Information Science and Technology. 2013: 738-743.
[5]	YAO B, LIU X, ZHANG W J, et al. Applying graph theory to the internet of things [C]//2013 IEEE International Conference on High Performance Computing and Communications and 2013 IEEE International Conference on Embedded and Ubiquitous Computing. 2013: 2354-2361.
[6]	WEST D B. 图论导论 [M]. 李建中, 骆吉洲, 译. 原书第2版. 北京:机械工业出版社, 2006.
[7]	BONDY J A, MURTY U S R. Graph Theory with Applications [M]. New York: The Macmillan Publishers, 1976.
[8]	高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社, 2009.
[9]	DIESTEL R. Graph Theory [M]. 于春林, 王涛, 王光辉, 译. 第4版. 北京:高等教育出版社, 2012.