图类中的序

图类中的弱良基序对一个图类的研究提供强有力的理论和计算手段。本项目要对一些典型图类和超图类进行在亚图包含意义下的弱良基序研究，从而对这些图和超图类的内部结构提供深刻的见解。结合计算和生成这项研究也附带对大规模集成电路中的代数与图论方法提供方法和基本计算方面的支持。所考虑的图类有最小度至少为4的3-连通图、平面二部图和极大平面二部图、连通正则超图、Halin图和推广的Halin图。通过亚图包含所给定的弱良基序我们还要对指定图类中的图一定包含的亚图和一定排除的亚图进行研究，对具有弱良基序的图类中大链和大反链进行研究，并对随机序进行基础研究。

设G是一个图.如果存在G的子图K和一个收缩映射(contraction mapping) f: K → H,那么图H叫做图G的一个亚图(minor). 用图的亚图包含关系作序可以得到图类中的几种重要的序关系.一类序关系是良半序(well quasi ordering).良半序是具有自反性和传递性的二元关系,其中每一个反链是有限的并且每一个严格降链是有限的.图类亚图定理[Robertson, Seymour: Graph minors. IV. Tree-width and well quasi ordering, J. Combin. Theory B48(1990), 227-254]证明了任意一个有限图的类在亚图包含关系下构成一个良半序.另一类序关系是弱良基序(well founded ordering).良基序是一个满足自反性,弱反对称性和传递性的二元关系,其中每一个严格降链是有限的.严格降链有限这个条件是在代数学中常用的Jordan-Dedekind条件.标良基序是数学归纳法和计算机科学中可计算性理论的基础.不仅是代数学和几何学,在图论和组合数学中有一系列具有若良基础序的类.关于球面三边形剖分的Steinitz-Rademacher定理,Tutte1961年关于3-连通图的重要定理,关于连通度的Menger定理,关于平面性的Kuratowski定理,亚图定理都是在图论中的重要例子.这些定理提供了研究的理论方法和实际的计算手段. 国家自然科学基金(10971027号)支持下进行的关于图类中的序的研究中,我们得到了以下结果:(1)最小读不小于4的3-连通图以及4-连通图的约化定理;(4)简单一致超图的约化定理;(3)另外一些额外结果在三篇已经发表的文章中.