第七讲、弦图与相似图

《第七讲、弦图与相似图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第七讲、弦图与相似图本讲中我们将结束对弦图的讨论。我们还将给出子树的相交图的描述，它很好地推广了区间图性质。同时我们将总结弦图的一些结论。我们将介绍相似图以及有效地解决判定、最大团、顶点染色等问题的算法。1．介绍我们知道弦图有两个等价命题：不含无弦的环；有完美消除序列。现在我们给出另一个等价命题：弦图可以表示为某个树的某个子树集的相交图：定理1：有N个顶点的图G＝（V，E）是弦图，当且仅当存在一棵树T的N棵子树T1..Tn，满足（Vi，Vj）∈E，当且仅当Ti∩Tj≠∅。（图1）这是我们要证明的首要结论。我们同时介绍相似图的概念。2．子树集的相

2、交图定义2：给定一棵树T及其若干子树T1..Tn。令V＝{V1..Vn}，E＝{ViVj

3、Ti∩Tj≠∅}，那么G＝（V，E）称为子树集{Ti}的相交图。这个定义有些不严密。我们申明：这里两个子树相交表示它们有公共边。另外，没有任何子树完全包含与另一棵子树。事实上这个申明并不是很实质，请看下面的引理：引理3：已知子树集T1..Tn，令G是它们的相交图，则存在另一个子树集T1’..Tn’，满足它的相交图G’与G同构，并且对任何Ti’，Tj’，i≠j，都存在边e满足e∈Ti’，e∉Tj’。证明：对于那些包含于其他树的子树，只要在其中某个顶点上增加一

4、条新边即可。▋注意引理2的否命题是错的，因此我们可以将定义2如下描述：定义4：给定一棵树T及其若干子树T1..Tn。令V＝{V1..Vn}，E＝{ViVj

5、Ti∩Tj∩E(T)≠∅}，那么G＝（V，E）称为子树集{Ti}的边相交图。注意定义4中的子树不满足Helly性质（见定义5）。显然，有定义4确定的图总是有定义2确定的图的子图。另外任何由定义2确定的图都能用定义4确定，证明类似引理3，但反之则不一定。（见图2，无弦环C4）因此我们可以假定子树互不包含且使用边相交。实际中，这些都将被用到，以上引理证明了这些假设不会改变图类型。以后我们将不在重

6、申这些条件。证明定理1之前，我们先回忆一下。我们曾证明N个顶点的区间图可以用一系列端点不重合的闭区间表示，并且这些端点可以离散到1至2N间的整数。事实上，我们证明了区间图是一条线段的若干子线段形成的相交图。因此，定理1是由区间图到弦图的一个更一般的描述。容易得知线段的相交图是子树集的相交图的特例。图3表示前者可以转化为后者；图4是后者无法转化为前者的一个例子。注：图4表明是一个一般性的方法：对于一棵树T，对它的每个顶点定义一棵子树为该点于它的所有子节点诱导的子树，那么这些子树形成的相交图就是T本身。3．定理1的证明这里我们只处理两子树相交是顶点

7、相交的情形（即定义2的情形）。定义5：令A为一个集合集，如果对于A的每个满足以下性质的子集A1：对所有Ai，Aj∈A1，UA∈A1A≠∅都有Ai∩Aj≠∅；都有，那么称A满足Helly性质。Helly性质表示两两相交等价于有共同的交集。为了知道这对子树集成立，考虑这样的一种情况：T1，T2，T3是T的三个子树两两相交，但却没有公共的交集。令Vij是Ti与Tj交集中的一个顶点，1<=i

8、23与P13。这三条路径构成T中的一条回路。由于V12、V23、V13互不相同，这个回路至少包含一个长度不小于3的简单环，这与T是一个图矛盾。对于多于三个的情况是类似的。我们首先证明有子树集形成的相交图都是弦图。证明：给定树T与子树集T1..Tn，我们对

9、T

10、用归纳法：

11、T

12、＝1时，T是平凡图，即Ti＝T，i=1..n。相交图是完全图，属于弦图。

13、T

14、≥2时，T含有一个叶节点V。有两种可能。如果没有子树恰在V相交，那么我们将V从T及所有包含它Ti中删去，相交图不会改变。由归纳假设，这个图是弦图；如果存在两个子树恰在V相交，由于V是叶节点，必有一

15、个子树仅含V一个节点，不妨设为Tn。注意与Tn相交的任何其他子树都包含V，也就是说所有与Tn相交的子树两两相交。那么在相交图中Tn的所有相邻点形成一个团，即Tn代表的点是单纯点。根据归纳假设，T中V后的相交图存在完美消除序列，将Tn代表的点加在最后，则整个相交图有完美消除序列，即这个图是弦图。即证。▋下面我们证明每个弦图都能表示为一个子树集的相交图。证明：我们一步步地建立树T，每增加一个顶点就增加一个子树。令G是一个弦图，它有一个完美消除序列{V1..Vn}。首先令T＝T1＝K1。对于i＝2，3…n，注意Vi的前驱对应的子树两两相交。由于满足H

16、elly性质，这些子树至少有一个公共点P。在T中加入一个新顶点Q，Q只与P相联，并将Q与边（P，Q）加入所有Vi的前驱对应的子树，最后令Ti＝{Q}。