曲面嵌入图的圈基  

Cycle bases of network graphs on surfaces

作　　者：王艳 周金秋 卢成晓 WANG Yan;ZHOU J in-qiu;LU Cheng-xiao(School of Mathematics and Statistics,Minnan Normal University,Zhangzhou 363000,China;Faculty of Scierce,Jiangxi University of Science and Technology,Ganzhou 341000,China;School of Mathematics and Statistics,Linyi University,Linyi 276005,China)

机构地区：[1]闽南师范大学数学与统计学院,福建漳州363000 [2]江西理工大学理学院,江西赣州341000 [3]临沂大学数学与统计学院,山东临沂276005

出　　处：《青海师范大学学报（自然科学版）》2018年第4期15-18,共4页Journal of Qinghai Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(11671186);福建省自然科学基金项目(2017J01404);福建省高校青年自然基金重点项目(JZ160455);闽南师范大学博士基金项目(L21327)

摘　　要：圈基常用于描述图的圈结构.在实际应用算法中,算法的复杂度取决于圈基的选择.圈基的长,即其包含的边数,直接影响算法的速度.2-连通图G圈基长的一个下界是2 |E (G)|-|V (G)|,其中V (G)和E (G)分别是顶点集和边集.若图G包含长为2 |E (G|)-|V (G)|的圈基,则它是平面图.本文应用曲面嵌入图理论将这一结果推广至曲面嵌入图上.A cycle base is used to examine the cyclic structure of a graph.In many algorithms related to graphs,the amount of work is dependent on the cycle base chosen.The length of a cycle base is the number of its edges in it.A cycle base with shorter length may speed up the algorithm.A lower length bound of cycle bases for a 2-connected graph Gis 2 |E(G)|-|V(G)| where V(G)is the vertex set of Gand E(G)the edge set.It implies that the graph G with a cycle base of length 2 |E(G)|-|V(G)| is planar.In this paper,we improve this result for graphs on surfaces by graph embedding theory.

关 键 词：圈基 圈基的长 曲面嵌入图 

分 类 号：O157.5[理学—数学]