毛虫图的带宽

求出毛虫图的带宽的计算公式并给出一个较简洁的证明，讨论了此带公式的计算复杂性问题，提出一种更简单的算法。     

求任意k值的基本互补划分—通用算法及计算机实现

本文从文献[8]中所建立的混合树的概念出发,进一步提出了混合外向树、始点分裂树的新概念,阐明了一种特定的序列与始点分裂树、混合外向树与基本互补划分之间的一一对应关系,基于这些关系,导出了一种通用算法,从而可方便与有效地产生k为任意值时的全部基本互朴划分,按这一算法所编制的程序已在计算机上成功地实现。     

几个特殊图类的全色数

对于几个特殊的图类Ｇ，本文证明了ｘＴ（Ｇ）≤Δ（Ｇ）＋２。     

平面图中的多商品流

本文讨论了源汇对间添加一条边后所得的网络图为平面网络图的情况下,如何求有可行流存在的网络中的多商品流,提出了求解多商品流的多项式时间算法,其运算复杂度函数为O{(n k-1)nlnn[|E(Q_(1e,max))|-1]}。作为此算法的应用,讨论了运输网系统如何合理安排商品的流量及流向的问题。     

对称旅行售货员问题局部搜索邻域的计数

旅行售货员问题(TSP)是图论、组合最优化和计算机科学中所熟知的.为了分析局部搜索算法的效果而提出如下的计数问题:给定完全图K_n的一个哈密顿圈C??,通过替换其中λ条边,可以得到多少个不同的哈密顿圈呢?[3]的作者已对非对称TSP解决了上述计数问题.本文将就对称TSP这一更困难情形给出相应的结果.     

平面连通图为哈密顿图的一个充要条件

本文利用对偶的概念，给出了平面连通图为哈密顿图的一个充要条件。 定理 平面连通图G（V≥3）为哈密顿图的充要条件是存在G的对偶图G＊＝（V＊，X＊）满足： （１） Ｖ＊ ＝Ｖ１＊：Ｖ２８，Ｖ１＊∩Ｖ２＊＝，Ｖ１＊≠，V２＊≠ （２）Ｖ１＊和Ｖ２＊的诱导子图＜Ｖ１＊＞和（Ｖ２＊）均是树。     

Mobius带型格子图的优美性

考虑Ｍｏｂｉｕｓ 带型格子图的优美性问题，证明了Ｍ（ｎ，２）是优美图，并提出了猜想：所有的Ｍ（ｎ，ｍ）都是优美图。