一个关于近-三角剖分嵌入的内插定理

一个近三角剖分嵌入是指一个图嵌入在一个曲面上,使得至多可能有一个面不是三角面。在本文中我们证明了如下结果：如果一个图G在某个可定向曲面S_h上有三角剖分嵌入,那么G在S_k上有一个近三角剖分嵌入,这里k=h,h 1,…,[β(G)/2],而β(G)是图G的Betti数。     

图的最大亏格的一个性质

本文所考虑的图均指有限元向图，没有解释的术语和记号同[1]．一个图称为简单图如果不含重边及环．曲面S这里指一个紧的，连通的，2－维闭流形（定向或不可定向），其亏格记为g（S）．连通图G在曲面S上的一个2－胞腔嵌入意指存在一个1－1连续映射h：G→S使得S＼h（G）的每个连通分支与圆盘拓扑同胚．连通图G的定向亏格γ（G）（或不可定向亏格γ（G））是指最小的整数k使得G在亏格为k的定向（或不可走向）曲面S上有2－胞腔嵌入；而图G的最大定向亏格，也常称之为最大亏格，记为γM（G）,是指最大的整数k使得G在亏格为k定向曲面S上有…     

关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

一个关于球面和环面上嵌入图的近-三角剖分嵌入的内插定理(I)

一个近-三角剖分嵌入是指一个曲面上的嵌入图使得几乎所有的面都是三角形,至多只有一个可能的例外.文中作者证明了如下结论:如果一个图G 在球面S₀(或环面S₁)上有近-三角剖分嵌入,那么G在每一个可定向曲面S_k有近-三角剖分嵌入,其中k=h,h+1,\cdots ,\lfloor\frac{\beta(G)}{2}\rfloor$, 而h=0(或1)并且β(G)是图G的Betti数.特别地,G是上可嵌入的.     

图的可定向嵌入的标根可数性

给定一族图G,可定向曲面上存在多少个以其中某个图为基础图的标根地图？采用图的自同构群对图在可定向曲面上的嵌入集合进行分类，该文解决了这个问题，同时得到了求解计数函数f^r(M)的一种新的方法。     

基本圈与图的曲面嵌入

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

不可定向曲面上的最大亏格嵌入和最小亏格嵌入

研究了不可定向曲面上最大亏格嵌入的估计数,得到了几类图的指数级不可定向最大亏格嵌入的估计数的下界.利用电流图理论,证明了完全图K_(12s)在不可定向曲面上至少有2~(3s-1)个最小亏格嵌入;完全图K_(12s+3)在不可定向曲面上至少有2~(2s)个最小亏格嵌入;完全图K_(12s+7)在不可定向曲面上至少有2~(2s+1)个最小亏格嵌入.     

可定向曲面上具有较短不可收缩圈图嵌入的唯一性

拓扑图论中的一个基本问题就是要决定图在一个(可定向)曲面上的嵌入之数目(既嵌入的柔性问题).H.Whitney的经典结果表明:一个3-连通图至多有一个平面嵌入;C.Thomassen的LEW-嵌入(大边宽度)理论将这一结果推广到一般的可定向曲面.本文给出了几个关于一般可定向曲面上嵌入图的唯一性定理.结果表明:一些具有大的面迹的可定向嵌入仍然具有唯一性.这在本质上推广了C.Thomassen在LEW-嵌入方面的工作.     

类圈图的亏格分布

一个图 G 的亏格分布是指序列{g_k}, g_k表示 G 嵌入亏格为 k 的闭的可定向曲面的数目. 该文给出了标准类圈图的亏格分布的递推公式, 并得到类圈图的嵌入多项式的计算公式.     

高校应用数学学报 第16卷(2001年)B辑(英文版)第2期目次和提要

完全二部图的 K1 ,pk-因子分解杜北 (苏州大学数学系 )给出了完全二部图 Km,n的 K1,pk-因子分解的一个充分条件 ,其中 k取素数幂 pk.这个充分条件是 :(1 ) m≤ pkn,(2 ) n≤pkm,(3 ) pkn-m≡pkm-n≡ 0 (mod(p2 k-1 ) ,(4) (pkn-m) (pkm-n)≡ 0 (mod(pk-1 ) pk(p2 k-1 ) (m+n) ) .极大平面图在不可定向曲面上强嵌入的一个注记刘同印　刘彦佩 (北方交通大学数学系 )证明了每个极大平面图 G=(V,E)在亏格最多为 (|V|-2 ) /2的不可定向曲面上存在一个强嵌入 ,使得其曲面对偶仍为平面图 .作为推论 ,得到 G在不可定向曲面上强嵌入的一个插值…     

两类四正则图的完全亏格分布

一个图G的完全亏格多项式表征了图G的亏格(可定向,不可定向)分布情况.本文利用刘彦佩提出的嵌入的联树模型,得出了两类新的四正则图的完全亏格多项式,并推导出已有结果的两类图的完全亏格多项式.此处的结果形式更为简单.     

图的不可定向最大亏格

本文证明了:对于任何一个有圈连通图G,其不可定向最大亏格为这里,α₀,α₁分别为G的顶点和边的数目.从而,也解决了图的不可定向嵌入的存在性问题.     

G(2m+1,m)的不可定向强最大亏格

图G的最大亏格指图G能嵌入到亏格为k的曲面的最大整数k.对于广义Petersen图G(2m 1,m),当m=1,4(mod 6),给出了最大亏格的表达式,对其余形,给出了不可定向强最大亏格的上界和下界.     

K_(1,4)梯图的可定向嵌入亏格分布

本文主要运用刘彦佩提出的联树嵌入法研究一类新图-K_(1,4)梯图W_n的可定向嵌入亏格分布,并通过进一步递推化简,得到了K_(1,4)梯图在小亏格上的嵌入亏格多项式显式,以及在其他亏格上的简单递推式,使其在可定向亏格上的嵌入个数更容易地得出.     

曲面上图的拉普拉斯谱半径

本文研究了图嵌入到给定紧致曲面上的拉普拉斯谱半径,确定了将顶点数为n、最大度为△的图分别嵌入到亏格为g的定向曲面和亏格为h的不可定向曲面上的新上界.     

关于嵌入图的最大亏格

不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格.     

图论与中学数学竞赛(二)

六平面图平面图一个图G,如果能够把它画在平面上,且除端点外任意两条边均不相交则称G可以嵌入平面,如果图G可以嵌入平面,则称G为可平面图可平面图在平面上的一个嵌入称为一个平面图,如图17—a所示的图G是一个可平面图。图17-b所示的图G是G的一个平面嵌入即平面图。     

树环中的流量疏导问题研究

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的映射树,称为超边在G中的嵌入问题.超图在树环中的嵌入问题即为寻找H在G中的最优映射使得G中任一边被H所有超边的映射经过的最大次数最小.应用超图嵌入圈(MCHEC)问题的算法可得超图嵌入树环问题的一个2-近似算法.     

消圈数与图的嵌入（英文）

设▽(G)表示最少的点数,这些点去掉后图中无圈(即森林).称这个数▽(G)为图G的消圈数.通常,确定图的消圈数是NP完全的.Bau和Beineke曾提出以下问题:哪些阶数为n的3正则图G的消圈数满足▽(G)=[(n+2)/4]?本文回答了这个问题:阶数为n的3正则图G的消圈数满足▽(G)=[(n+2)/4]当且仅当G是上嵌入的(即以最多两个面嵌入在可定向曲面上).其次,对于一般3正则图,得出其消圈数的计算公式为▽(G)=γ_M(G)+ζ(G),这里γ_M(G)表示图的最大亏格,ζ(G)表示图G的Betti亏数.由此可知,3正则图的最大亏格的计算的多项式算法是存在的,所以3正则图的消圈数的计算也是多项式可解的.     

顶点劈分与图的上可嵌入性（英文）

一个图G的弱子式G是通过对G进行边收缩得到的.一个弱子式封闭的上可嵌入图族是一个上可嵌入图的集合,并且该集合中任何图的弱子式仍在这个集合中.目前关于判断图的上可嵌入性的充要条件很少.本文通过研究顶点劈分与图的上可嵌入性的关系得出一个判断图的上可嵌入性的充要条件;给出了一个从环束出发构造弱子式封闭上可嵌入图族的方法;推广了[J.Graph Theory,1981,5(2):205-207]的一个结论.并且,用本文所得结论判断图的上可嵌入性时其算法复杂度会得到很大降低.