图与超图的若干参数及其在数据结构中的应用

基于超图的数据结构以超图和集合理论为基础，可以表达空间数据之间的层次关系和横向关系，使空间数据结构在空间分析中的完备性和适应性问题得到解决。超图的出现,使得多层次,多功能的拓扑关系表现成为可能. 本项目研究图与超图中的几个参数。（1）刻画某些超图的度序列；（2）试图用随机方法或分析的方法给出一些超图类的独立数，色数。（3）以Erdos关于超图的二着色的一个极值问题的猜想为猜想为主攻目标，试图改进已有的m(n)的上下界。（4）结合组合、代数和随机方法,利用First-first, Labeling method, Dynamic programming, Primal-dual approach等算法思想和设计手段来研究讨论染色和控制集方面的若干问题。（5）同时，我们将考虑图中一些染色以及控制集的结果推广到超图上的可能性。

我们基本按计划书的内容进行研究。本项目主要研究图与超图中的如下几个问题: 1. 研究r-一致超图的独立数。2. 研究不含3-圈或者不含4圈的平面图的性质。3. 研究平面图的Ramsey数。4. 研究平面图的独立数。5. 研究图的L(2,1)标号问题。6.研究图的控制集与控制数问题。关于超图的度序列问题，由于国际上关于该问题的进展，该部分内容有所调整。 在本项目经费资助下，本项目共取得论文11篇，其中已发表6篇，接收2篇。