图的上可嵌入性

证明了一个连通无环图G如果能嵌入某个 (定向或不可定向 )曲面S上使得每个面的大小不超过 5 ,则G是上可嵌入的 .     

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

本文给出了由边数和根面的次作为指标的有根不可分离平面偶地图的计数函数所满足的函效方程,此方程是三次的。而,有根一般平面偶地图的相应计数函数所满足的方程却是二次的。从此后一个方程出发得到了上面提到的二个计数函数的具体形式。同时,发现了这个有根不可分离平面偶地图的计数函数与Fabonacci叙列的关系。     

关于有根简单平面三角地图数目的一个注记

一个地图,指图在某曲面上的一个嵌入.平面地图,自然就是在平面上的嵌入.三角平面地图,即所有面皆三角形的平面地图.一个地图,如果将它的一条边规定一个特殊的方向,此边称为根边.根边的始端称为根点,沿根边的方向走左手边的面称为根面,则这时称这个地图为有根的.之谓二个有根的地图是不同的,或曰组合上不等价,指二者之间不存在一个同构映像使得它们根点、根边和根面也相应.可想而知,研究有根地图的组合不变性与研究一般地图的组合不变性在根多情况下是一致的.特别是在着色理论中有根和无根一个样.然,     

关于平面树色和方程结果的一个注记

这篇文章得到了有根平面树的节点剖分的色和方程. 导出了带无限多个参数的有根平面植树和平面树的色和方程的精确表达式. 作为直接推论可推出节点剖分的有根平面树的计数方程的精确结果 .     

我所了解的图论(四)

第六讲群与图——图论中的对称性在我介绍关于拼方的早期工作时,曾提及四名研究者怎样从Brooks太太那里了解到在他们的图中对称性的重要.现在,我打算较详细地谈谈对称性.他们处理的对象称为“转子”,即具有旋转对称性的图.一个图称为转子,若它是连通的且具有一个有限阶n的自同构θ.即自同构θ,θ~2,…,θ~(n-1)互不相同,而θ~n是恒等自同构I.而且,这个图一定要有n个“边界”顶点集A_1,A_2,…,A_n=A_o,它们在由θ生成的循环群之下是等价的.就是说,它们满足     

序关系与0—1规划问题(下)

§ 9 集 合 组 装 问 题 以下,我们讨论如§5中所给出的准序。对于一个集 合XB_1~n,如果x=(x_1,x_2,…x_n)∈X,存在N={1,2,…,n}上的一个置换π使得 有x_(π(1))x_(π(2))…x_(π(n)),即 对于X是一个线性序,则称X是正则的。 相仿地,对于一个布尔或拟布尔函数f,也可建立准序:     

有根无环平面地图节点剖分计数方程

一个平面地图,如果无有边是环,则称为是无环的.有根的意义与[1]中的相同.在那里对于此类地图的一些计数问题作了研究,但从未触及到节点剖分.这篇文章的主要目的在于研究这类地图的依节点剖分的计数.求出了有根无环平面地图依节点剖分计数的母函数所满足的一个泛函方程.并且,作为这一方程的一种应用,求出了一类在节点的最大次给定情况下的有根无环平面地图依节点剖分计数的一些结果.     

Steinhause棋盘问题的一个推广

In the present paper, a generalization of Steinhaus' chessboard problem of 8 × 8 and that of m×n are given and its solution is proved. Then, Steinhaus' chessboard problem is directly solved as a corollary, and the m>n case is solved immediately.     

ON THE VERTEX PARTITION EQUATION OF ROOTED LOOPLESS PLANAR MAPS

This paper provides a functional equation astisfied by the generating function for enumerating rooted loopless planar maps with vertex partition. A kind of applications in enumerating, by providing explicit formulae, a type of rooted loopless planar maps with the maximum valency of vertices given are described. Meanwhile, the functional equation for enumerating rooted loopless planar maps (connected) with the edge number and the valency of root-vertex as the parameters is also derived directly.     

CHROMATIC SUM EQUATIONS FOR ROOTED CUBIC PLANAR MAPS

This paper provides a functional equation satisfied by rooted nearly cubic planar maps.By anearly cubic map is meant such a map that all the vertices have valency 3 with the exception of at mostthe root-vertex.And,as a consequence,the Corresponding functional equation for rooted cubic planarmaps is found.