关于图的Hamilton性

凡未作解释的术语均可参考Bondy和Murty的书。 一个图G=(V,E),如果满足如下的性质A和B,则称之为核心图。所有核心图的集合记为。 性质A存在一个整数K≥1使得:(i)V=V_o V_1 … V_k;(ii)G[V-V_o)=G[V_1)     

组合最优化中的布尔方法

本文旨在从NP-完全性理论的角度,以拟布尔函数最优化为典型实例介绍组合最优化问题的一些研究方法和取得的主要进展。并且也提出了一些有待解决的问题和可能的研究途径。     

COUNTING ROOTED EULERIAN MAPS ON THE PROJECTIVE PLANE

1IntroductionAsurfaceisacompactclosed2-manifold.Theorielltable(non-orielltable)surfaceofgenuskisthespherewitllkhandles(crosscaPs)denotedbySk(Nk).AmapMollSk(Nk)meansthatitsunderlyinggraphnlaybedrownou(embeddedin)itsuchthatllthpairofedgesintersectataninnerpoilltalldeachfaceishomeomorphictothedisc.Amapisrootedifanedgewithadirectiollalongtheedge,alldasideoftl1eedgeisdistinguisl1ed.Tworootedmapsareconsideredtobethesal11eifthereisanisomorphismpreserviIlgtl1erooting.ArootedEuleriall1llapissuchaon…     

依节点剖分数树的一种新方法

本文提供一种直接的初等方法依节点剖分数树, 而不是用已知的递推关系、母函数、泛函方程、Lagrange反演、无限维矩阵等.     

球面和射影平面上不可分地图的色和

给出了球面和射影平面上带根不可分地图的色和方程,从色和方程导出了球面和射影平面上带根一般不可分地图、二部地图的计数函数方程. 利用色和理论,研究不同类地图的计数问题,得到了一种研究计数问题的新方法. 此外,还得到了一些计数显示表达式.     

多重跳图的平面性

The infinite sequence {J^k5(G)} where Js(G) denotes the 5-jump graph of G, is planar if, and only if, G=cor(K3). For r-jump graph with r≥6, there does not exist a graph G such that the sequence {J^kr(G)} is planar.     

关于3—正则子图问题的一个注记

这篇注记证明判断一个图是否有３－正则子图的问题，即使对于节点次不超过４的平面力，仍然是ＮＰ－完全的，而且，此结果是最好的可能。     

纵横扩张的优化

得到了最小折数纵横扩张的判别准则．针对4-正则图的平面嵌入的纵横扩张的特殊性，给出了它的最小折数纵横扩张判别准则．     

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

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

地图着色定理与图的曲面嵌入(Ⅲ)

<正> 用Z_(12s+6)(I)带附加条件 d3,若在一个次为3的顶点处有三个字母,如a,b,c,则各边流入的电流只能mod 3余1或2.而且,三个流入电流之和是Z_(12s+6)的由3的倍数形成的子群的生成元. 先构造一个梳图Γ_(2s+1).然后,通过结构变换把它变为Z_(12s+6)(I)的中心部分.最后,添上首尾部分.