论文部分内容阅读
如果一个图的每一个顶点都可以与一个集合族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-探针区间图的两个线性时间的判别算法.
第六部分主要研究一些相交图类对应的边团图的性质.给定一个图,如何有效的判断它是否边团图仍然是一个尚未解决的问题.本文证明了可以在多项式时间内判断一个区间图或者探针区间图是否为边团图.并且本文对探针区间图和受限制的圆弧图这两种图类的边团图的性质进行了刻划.