基本圈与图的曲面嵌入  

作　　者：任韩[1] 赵洪涛[1] 李浩玲[1] 

机构地区：[1]华东师范大学数学系,上海200062

出　　处：《中国科学（A辑）》2009年第4期500-506,共7页Science in China(Series A)

基　　金：国家自然科学基金(批准号:10271048;10671073);上海市自然科学基金(批准号:07XD14011);上海市重点学科建设基金(编号:B407)资助项目

摘　　要：本文研究图的基本圈与图在可定向曲面上的嵌入之间的关系.本文结果表明:一个图G可以嵌入到亏格至少为g的可定向曲面上的充分必要条件是:对于G中任意一个支撑树T,存在一个基本圈序列C1,C2,...,C2g,使得对于每一个i:1≤i≤g,C2i-1∩C2i≠φ.特别地,在T的β(G)个基本圈中有基本圈序列C1,C2,...,C2γM(G),使得C2i∩1∩C2i≠φ对于每一个i:1≤i≤γM(G)成立.这里β(G)和γM(G)分别是G的Betti数和最大可定向亏格.这个结果的意义在于:我们可以从任意一个支撑树(可以具有任意奇连通分支数)出发去构造图在可定向曲面上的嵌入.这在本质上有别于Xuong与Liu在最大亏格方面的工作(即,从具有最小奇连通分支数的支撑树出发构造图嵌入).事实上,这个结果在本质上同时推广了Xuong-Liu与Fu等在最大亏格方面的工作.作为这一结果的直接应用,本文得到以下结果:(1)提出了用于计算图的最大亏格的新条件,它尤其适用于计算具有特定边割(edge-cut)图的最大亏格.并得到一些新的与已知的著名结果(包括Huang在曲面嵌入图方面的工作).(2)最大亏格问题可以归结为在基本相交图中求最大对集问题.结合Micali-Vazirani的一个有效算法,我们设计出了一个用于计算图的最大亏格的多项式算法,它的复杂度是O((β(G))25),这一算法与Furst等人的算法相比更加直接、便于计算.

关 键 词：基本圈 最大亏格 上嵌入 

分 类 号：O157.5[理学—数学] TQ320.662[理学—基础数学]