一类布线问题求解的判别准则和算法

在已有的判决图的基础上,定义了方向性及导出判决图,找到了一个判断布线问题中的1-嵌入问题是否有解的准则和基于此判别准则的算法,并在此基础上进一步研究了禁用构形,找到了1-嵌入问题有解的另一个判别准则.     

关于无环Euler节点剖分方程

凡文中未解释的术语,在计数理论方面参见文献[1],在方程方面参见文献[2,3],在地图理论方面可参见文献[4]。 令N为有根平面地图的一个集合。对于N∈N,用m(N)和n_i(N)分别表示N的根节点的次和次为i的非根节点数目。我们这里所关心的是有根无环Euler平面地图。用     

联树模型在亏格等式证明中的应用

应用联树模型,把图浸入平面,获得这个图的关联曲面,从而获得这个图的嵌入曲面的亏格.应用这个方法,我们证明了2个著名的亏格等式.第1如果e是图G的一条割边,G-e有2个分支G1,G2,那么,g(G1) g(G2)=g(G).其中g(G)表示图G的亏格.第2用H*vK表示图H与K在点v处的结合,即V(H)∩V(K)=v,E(H)∩E(K)=φ.γ(G)表示图G的最小可定向亏格.那么,γ(H*vK)=γ(H) γ(K).     

类树图亏格分布的单峰性

图的亏格分布是否为单峰,这一猜想至今没有得到证明.文章首先给出了单峰性的概念及性质,并进一步推导得到了单峰性的另一重要性质。在此基础上,使用分类讨论的方法,证明了类树图的亏格分布是单峰的.     

格子状网络的最优连接及最优定位问题

数最短路问题（SPCP）在社会生活中有着广泛的应用，Oyama T和Taguchi A(1991)讨论了相同形状的格子网络的连接及中位与中心问题。该文进一步研究基于不同形状的格子网络的连接及连接后新网络的中位与中心问题，从而，Oymama T和Taguchi A(1991)所讨论的作为该文的特殊情形。     

面近正则外平面地图的色计数函数

首先给出了不可分离面近正则(除根面外,其它每个面的次均是常数k,其中k≥3)外平面地图的色数、根面次和边数3个参数的色计数函数所满足的方程,并给出了它的显式表达式.然后,给出了可分离面近正则外平面地图的色数、根面次和边数3个参数的色计数函数所满足的方程.     

一类图的强最大亏格嵌入

图的嵌入理论是拓扑图论中一个中心课题.图的最大亏格嵌入的刻画和研究已较完善.但对于强嵌入,这方面的讨论却很少.本文对于平面上的不含不交(指无公共节点)圈的图以及完全图K5,利用构造强最大亏格嵌入的方法,给出了强最大亏格.同时,也给出了完全二部图K3,k(k≥3)的不可定向强最大亏格的一个下界.     

关于有根外平面地图的着色计数

关于着色计数,Tutte于1973年发表第一篇文章,他所研究的是平面上的三角剖分。十年之后,本文作者研究了一般平面地图。接着,又研究了平面上的3-正则地图。这里所研究的是外平面地图并且求出了着色计数的显式。而文献[1-3]均未得到这样的显式。 当然,我们也是研究带根的情形。事实上并不影响问题的一般性。对于一类地图M,其着色计数函数为     

有根不可分离外平面地图的计数

令A(m,n),m,n≥1,为具有m条边且根面的次为n+1的有根不可分离外平面地图的数目。本文得到了:     

不可分离外平面地图节点剖分计数

全文只研究带根的地图。记N为所有有根不可分离外平面地图的集合。对于N∈N,令v=v(N)是根节点,r=r(N)是根边,m(N)是节点v的次,和n_i(N),i≥1,次为i的非根节点数。进而,应该指出,仅由一个节点而无边所成的地图,即节点地图,和仅有一边