论文部分内容阅读
如果一个图的每一个顶点都可以与一个集合族S中的一个集合相对应,使得两个顶点相邻当且仅当他们对应的集合相交非空,那么就称该图是S的相交图。相交图的应用背景涉及计算机,生物,矩阵分析,统计学等多个领域。而由于它的广泛应用性使得相交图理论在最近二三十年间得到了迅速的发展。本文正是针对相交图理论中的一些问题进行研究和探讨。主要讨论了在不同条件限制下的最节省的相交表示,相交数及表示的唯一性问题。并对一些重要的相交图类的性质进行了刻划。 本文的工作分为六部分。 第一部分是概述。主要讲述了相交图理论的研究背景和发展现状,并介绍了本文的主要工作。 第二部分主要针对没有条件限制的最节省的相交表示问题进行了研究。求任意一个图的相交数的问题是一个NP-难的问题[54]。我们可以通过分数相交数i_f(G)对相交数i(G)进行估计,并且对满足i(G)=i_f(G)的图类可以在多项式时间内找出它们的相交数的值。Scheinerman and Trenk[90]证明了如果一个图是弦图,那么i(G)=i_f(G)。本文推广了他们的结果,证明了如果一个图G的边团图是θ-弱完美的那么i(G)=i_f(G)。作为应用本文进一步从不同的角度对一些满足边团图是θ-弱完美的图类的性质进行了刻划,并且对它们之间的层次关系进行了描述。本文中还提出了一个贪婪算法,对任意的图都可以通过该算法找到它的一个相交表示。并且本文还证明对一些相交图类,如不受菱形约束的消去图等,都可以通过该算法在多项式时间内找到它们的最小相交表示。