第四讲、区间图及其补图

《第四讲、区间图及其补图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第四讲、区间图及其补图本讲中我们将讨论在一个区间图中寻找最大独立集的问题。我们还将研究区间图的补图与可无环传递定向图的关系。最后我们将介绍弦图的概念。1．介绍之前各讲中我们讨论了区间图，并知道一些典型的难题在区间图上可以高效地解决。有一些问题，诸如图的染色、最大团问题、哈氏回路问题以及判断两个图是否同构的问题都是NP难题。然而在区间图上，我们能出色地将这些问题在多项式（而且经常是线性）时间内解决。这一讲中将讨论的最大独立集问题就是其中之一。我们将使用贪心算法求出一个图的最大独立集，前提是该图具有完美消除序列并且这个序列已知。有关该问题的详细内容参见LornaStewar

2、t的主页http://web.cs.ualberta.ca/stewart/GRAPH/index.html。我们将了解的另一类图是区间图的补图。我们将学习一种对这些图的边的自然确定法，并发现区间图的补图实际上是相似图。最后，我们将介绍弦图并证明具有完美消除序列的图都是弦图。2．定义一个图G的独立集是它的一个边集为空的诱导子图。一个具有K各顶点的独立集称为K独立集。一个极大独立集是一个独立集，但加入任何其他节点都将破坏独立集的性质。一个最大独立集是G中存在的顶点数最多的独立集，记为。3．寻找独立集的一个可行算法以下算法用贪心法寻找图G的一个独立集。它不一定是极大（或最大

3、）的。算法的输入是图G以及一个顶点序列{V1..Vn}初始时记所有顶点未访问（untouched）。假设贪心算法的输入是一个完美消除序列，它能保证得到一个最大独立集吗？考虑图1所示的图G。显然这个图具有完美消除序列{V1,V2,V3,V4}。然而当贪心算法作用与该图时，它将找到独立集{V1}，这显然不是最大独立集。然而如果将完美消除序列的逆序作为输入，却可以得到最大独立集。定理1：如果{V1..Vn}是一个完美消除序列，那么以上贪心算法对与顶点序列{Vn..V1}可以得到最大独立集。证明：很容易得知完美消除序列的逆序具有如下性质：对于每个i{1..n}，{Vi}Succ

4、（Vi）是一个团。对与某个未方位的点Vi，它与它的后继中至多有一个在独立集中。如果这些点都不在独立集中，显然加入点Vi后仍是一个独立集，而且必原来更大；如果这些点中有某个Vj在独立集中，用Vi代替Vj，显然得到的仍是一个独立集，而且与原来一样大。综上所述，对任意一个不包含Vi的独立集，总存在一个包含Vi的独立集，且不比原来小，这对最大独立集同样成立，即Vi的贪心选择是正确的。定理1得证。▋另外，我们给出一个利用拟阵进行的证明作为参考：证明：建立拟阵M＝（S，I），S为图G的顶点集，按照完美消除序列逆序编号；I为G的独立集集合。显然I具有遗传性质。又设I中的两个元素A，B

5、，

6、A

7、>

8、B

9、，B中的每个顶点最多有一个后继属于A，否则由于B的后继集是一个团得出矛盾。因为

10、A

11、>

12、B

13、，A中必有至少一个元素V不是B中任何元素的后继，即将V加入B中，B仍是独立集。因此I满足交换性质。综上所述，M是一个拟阵。令每个S中的元素的权为1，则最大独立集问题转化为求拟阵的最大权独立子集问题。根据拟阵理论，贪心算法成立。定理1得证。▋通过运用以上一类算法，很多NP难题在区间图上能够用线性或多项式时间解决，这些问题包括图的染色、最大团问题、最大独立集问题、哈氏回路问题以及判断两个图是否同构。然而另一些问题仍然是NP难题，例如货郎问题：给定一些城市即之间的距离，

14、要求找出一条访问每个城市的最短路径。如果将城市看作顶点，距离作为边权，货郎问题就是在图中寻找包含所有顶点的最短路。由于可以在任意两个城市间行走，该图是一个完全图Kn。显然Kn（不包括边权）是一个区间图。4．区间图的补图许多情况下，一个图与它的补图属于同一类图。那么区间图也是这样么？构造一个区间图，完美在相交的区间之间连边。因此在它的补图中，每个顶点仍然代表一个区间，但两个顶点之间有边，当且仅当对应的区间不相交（见图2）。另外，边由左到右进行定向。给定一个区间图G＝（V，E），它的补图＝（V，DE），其中（u,v）DE，u,vV是一条u到v的有向边，区间Iu在Iv的左边。

15、定义1：图G＝（V，E）的一个定向图（又称竞赛图）是把E中的每条边（u,v）定向后得到的有向图。G的一个无环定向图是它的一个不含有向环的定向图。一个定向方法如果满足对所有u,v,wV，且u到v有边，v到w有边，则u到w有边，则称为具有传递性的定向。一个边定向无环且具有传递性的定向图称为无环传递定向图。定义2：具有传递定向图无环传递定向图的无向图称为相似图。补图是相似图的图称为伴相似图。显然一个区间图的补图是边无环可传递的。因此区间图的补图（不带方向）是可无环传递定向的，或者说区间图（不带方向）是伴可无环传递定向的。但区间图不一定是可无环传