2-Structures理论和图的模块分解中的右干问题

摘要

图论和组合数学是离散数学中的重要组成部分，在解决计算机中的算法和生物结构以及其他学科问题中都发挥着重要的作用，因此研究一个图的结构性质也显得更加重要了。
　　2-Stmctures理论和图的模块分解理论是在自然科学与数学中出现的一种重要的结构，它们在求解图的最优化问题中、算法图论、计算机科学、生物数学等领域都有着广泛的应用。同时图的2-Structures理论是研究图的分解理论的框架和基础，如对完全图的边着色问题。对图的modular decomposition研究主要产生于对不同的离散结构的探讨，如无向图、有向图、2-Structures，autom ata，Boolean functions，hypergraphs。图的modular decomposition在图论中有很多重要的应用，例如它能给出一个给定的可比较图的所有可传递方向计算框架；定义一些图类如cographs，P4-sparse或者P4-tidy。
　　本文首先对2-Structures理论中的经典理论进行了回顾。接着整理了2-Structures的shape的基本性质，以及2-Structures-labeled tree fam ily与labeled2-Structures之间的关系和性质。并就2-Structures理论中的若干引理和推论给出了新的证明并对定理2.3.27进行了推广。然后我们引入了图的module和modular decomposition理论，并对原有的理论进行了整理。接着讨论了图的m odule的基本性质，图的modular decomposition的一些重要定理。通过对图的module和modular decomposition理论的深入研究，结合自己的理解，得到了一些新结果。如对于一般简单图，它的任何两个模块之间的关系(定理3.3.1);对于一般简单图，如果此图是素图(即不含有非平凡的模块-所有模块都是平凡的)，那么此图关于平凡模块的商图在图的同构的意义下是一样的(定理3.3.6);如果图G是非初等素图，那么图G—定含有P1诱导的路径(定理3.3.7);对于一简单图G在满足某种条件下，其模块分解树一定是一棵二叉树(定理3.3.14);以及P i是最小的非初等素图(推论3.3.15)和观察(3.3.9): i)根据图的模块分解的定义，任何图都具有图的模块分解树；ii)如果对于一个顶点个数不小于4的简单连通图，如果其模块分解树是一棵二叉树，那么此图一定不是素图，且其不含有标号是N-n o d e的节点；iii)对于任何图，按其最大非初等模块分解得到相应图的商图，如此递推下去，最终只有两类图：素图和一个点的图；完全图的模块分解树是所有图中模块分树中深度最大的分解树，同时素图的模块分分解树是深度最小的。最后给出了2-Structures和图的module及其modular decomposition之间的某些联系。

目录

封面

声明

中文摘要

英文摘要

目录

符号说明

第一章 绪 论

第二章 2-structures 理论

§2.1 2-structures 综述

§2.2 2s的clans, 2s的基本子类

§2.3 2s标号树的表不论

§2.3.1 tree family和2s-labeled tree family基本性质

§2.3.2 2s的shapes的基本性质

§2.3.3 2s of 2s-labeled tree family

§2.3.4 Labeled 2-structures

第三章 图的module及其modular分解理论

§3.1绪论

§3.2图的m odular分解理论综述

§ 3 .2 .1准备知识

§ 3 .2 .2图的m odule及其分解的基本性质

§3.3图的m odular decom position的一些重要定理

第四章 图的 modular decomposition与2-strnctures之间的联系

第五章工作总结与展望

§5.1总结

§ 5 .2 展望

参考文献

附 录 一 致 谢