相交图论的若干问题

来源 :上海交通大学 | 被引量 : 0次 | 上传用户:y1271
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果一个图的每一个顶点都可以与一个集合族s中的一个集合相对应,使得两个顶点相邻当且仅当他们对应的集合相交非空,那么就称该图是s的相交图.相交图的应用背景涉及计算机,生物,矩阵分析,统计学等多个领域.而由于它的广泛应用性使得相交图理论在最近二三十年间得到了迅速的发展.本文正是针对相交图理论中的一些问题进行研究和探讨.主要讨论了在不同条件限制下的最节省的相交表示,相交数及表示的唯一性问题.并对一些重要的相交图类的性质进行了刻划. 本文的工作分为六部分. 第一部分是概述.主要讲述了相交图理论的研究背景和发展现状,并介绍了本文的主要工作. 第二部分主要针对没有条件限制的最节省的相交表示问题进行了研究.求任意一个图的相交数的问题是一个NP一难的问题[54].我们可以通过分数相交数if(G)对相交数i(G)进行估计,并且对满足i(G)=if(G)的图类可以在多项式时间内找出它们的相交数的值.Scheinerrnan and nenk[91]证明了如果一个图是弦图,那么i(G)=if(G).本文推广了他们的结果,证明了如果一个图G的边团图是θ-弱完美的那么i(G):if(G).作为应用本文进一步从不同的角度对一些满足边团图是θ-弱完美的图类的性质进行了刻划,并且对它们之间的层次关系进行了描述.本文中还提出了一个贪婪算法,对任意的图都可以通过该算法找到它的一个相交表示.并且本文还证明对一些相交图类,如不受菱形约束的消去图等,都可以通过该算法在多项式时间内找到它们的最小相交表示. 第三部分是对有条件限制的最节省的相交表示问题进行研究.本文分别给出了异相交数和Helly异相交数的一个下确界.并对取到最小确界的极值图的性质进行了刻划. 第四部分对一些图类的唯一可表性进行了讨论,特别是上一部分中提到的极值图的唯一可表性.这是对Mahadev and Wang[59]关于唯一可表性结果的推广. 第五部分中通过引入顶点集合的一种线性排序,本文对探针区间图的性质进行了刻划.并给出了STS-探针区间图的两个线性时间的判别算法. 第六部分主要研究一些相交图类对应的边团图的性质.给定一个图,如何有效的判断它是否边团图仍然是一个尚未解决的问题.本文证明了可以在多项式时间内判断一个区间图或者探针区间图是否为边团图.并且本文对探针区间图和受限制的圆弧图这两种图类的边团图的性质进行了刻划.
其他文献
本文主要研究了线性互补问题的MAOR迭代法、广义垂直线性互补问题、广义垂直线性互补问题的MAOR迭代法以及矩阵Perron根估计.全文共分为四部分. 第一部分主要考虑线性互补问
美国著名化学家M.Randic为了研究饱和碳氢化合物的碳原子骨架的分支程度,在1975年提出了一种重要的分子拓扑指标(Randic指标)。调和指标为Randic指标的另一种形式,记为H(G),其中
鲜绍堂,重庆人,1949年出生,字子鸣,笔名末流,重庆电视艺术家协会会员,现任重庆市巴渝文化研究院书画艺术中心主任、重庆艺术家沙龙协会会长、编剧。作者擅长小说、戏剧创作,
期刊
期刊
海峡导报2013-02-05报道:根据国家质检总局《进境木质包装检疫诚信管理指南(试行)》,厦门检验检疫局从本月1日起试行进境木质包装检疫诚信管理,于一个记分周期,也就是一个季
随着国家对职业教育越来越重视,在大力发展职业教育背景下,为社会培养高质量的技能型人才是各个中职学校的首要目标,因此CDIO工程教育模式在中职学校的应用和推广越来越多,本
混沌现象广泛存在于客观世界中,对混沌现象的认识是非线性科学最重要的成就之一。随着对混沌现象研究的不断深入,混沌控制和同步成为这一领域的前沿课题。而时滞和脉冲是混沌现
滑坡是地壳表层岩体的一种地质突变现象,是一种多发性地质灾害。近年来,随着我国能源开发及基础建设的不断深入,我国面临前所未有的工程地质灾害问题,在没有足够的经济技术力量对
期刊