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

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:haha123456hehe
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论和组合数学是离散数学中的重要组成部分,在解决计算机中的算法和生物结构以及其他学科问题中都发挥着重要的作用,因此研究一个图的结构性质也显得更加重要了。  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之间的某些联系。
其他文献
人个期货交易系统(以下简称期货交易系统)是对期货市场交易全过程(包括进场,出场,风险控制,利润控制等)的各个环节作出全面投资决策的一整套明确规则的体系,它为投资公司或投
该文主要讨论多电极成象测井中的偏微分方程反问题,将其化约为一个多参数辩识问题,分别用拟牛顿方法和遗传算法进行求解.
该文对一类多层规划问题(包括线性和非线性情形)进行了分析,并且给出相应问题的求解算法.前言部分叙述了多层规划问题的实际背景和具体应用;第二章详细探讨了一类线性多层规
该文给出了一套基于模糊数学方法,利用完工程数据对拟估工程进行快速估价的新方法,详细描述了全新的贴近度算法,构造了工程估价的模糊线性加权模型.同时,从建模角义入手,利用
随着勘探程度的精细与加深,能够反映储层的地震特征参数在油气预测中显示出来越来越重要的价值,但不同的方法所提取出的各种地震特征参数在预测油气能力上是不同的.该文针对
该文讨论半正边值问题正解的存在性,即研究人员允许非线性项取负值,通过运用锥上的不动点定理,获得了几类半正边值问题正解的存在性结果,一定程度上改进和完善了该领域内的一
该文讨论了空间飞行器控制实验室实验(SCOLE)模型的反馈镇定问题.物理模型为末 端带有刚性体的弹性梁,作用力和转矩加在刚体上.作者研究这个混合系统的基的性质,谱确定增长条
该文对富裕性疾病进行研究,提出了一个描绘患病与否及其严重程度的概念:患病度.并对几种富裕性疾病给出了患病度的具体定义及计算方法,在某些情况下,还研究了患病度的年龄分
1952年Markowitz开创性论文"证券组合选择"的发形标电着现代证券组合理论的诞生.在其后的四十多年里,证券组合理论得到蓬勃发展,取得丰硕的成果.这些理论研究都是以西方成熟