第十二讲、相交图

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

1、**第十二讲、相交图本讲中我们将介绍相交图与它的一些特例，如边图、圆弧图、T－区间图和正交图，以及这些图的基本性质、判定、染色、独立集、与其他类型图的关系等问题，但多数将不给出证明。（除了译者自证的）1．介绍我们已经了解了一些相交图，例如区间图、弦图、排列图等。许多现实问题都可以转化为相交图上的问题。由于相交图的范围广泛，它包含一些特例，例如边图、T－区间图、圆弧图、正交图等。图的判定、独立集、染色、团、与其他类型图的关系等是图论中的一些经典问题，多数情况下这些都是NP问题，但对于某些探索的相交图，部分

2、问题可以有效解决。第2解中将给出相交图的定义并进行简要的讨论。之后几节将逐个讨论一些相交图的特例。2．相交图定义1：一个图个是相交图，如果它的每个顶点V可以映射到一个集合Sv，满足两个顶点间有边，当且仅当它们对应的集合的交集非空。定理1：所有的图都是相交图。证明：令Sv＝{以V为一个端点的边集}。显然若（V，W）有边，当且仅当该边是V、W对应集合交集中的元素。即证。▊问题1：有定理1的证明可知一个元素个数为

3、E

4、（边数）的全集中的若干子集的相交图可以成为这个图G＝（V，E）。但是更小的全集是否可行呢？全

5、集元素的下界又是什么？这是一个开放的问题。3．边图定义2：一个图G的边图H满足V（H）＝E（G），H中两个顶点间有边，当且仅当它们对应的边在G中有一个公共端点。图1中白点与虚线显示了一个图的边图。显然一个五阶的无弦环的边图是它本身，即一个洞，所以边图不一定是完美图。3．1．边图的一些结论假设图G的边图是H，下边是一些经典问题在H上的一些结论，这里不加证明。ò判定：边图可以在O（n+m）时间内判定，具体方法见[Rou73,Leh74]。ò独立集：边图上的最大独立集问题就是原图G上的最大匹配问题，由于最大匹

6、配在任意图上都可以有效地解决（一种方法是利用带花树），因此边图的独立集问题也是可解的。ò团覆盖：这个问题就是原图的的顶点覆盖问题，这是一个NP问题。但当G是二分图时这个问题是可解的。ò染色：这个问题等价与原图的边染色问题，也是NP问题。但可以得知图G的边色数要么等于度最大顶点的度，要么等于这个数加1，因此搜索时有较强的剪枝。【而且对于二分图，有边色数等于度最大顶点的度】，因此是可解的。ò团：边图H中的团对应的原图中的边要么是三角形，要么交于同一点（很容易理解和证明），因此只要测试原图中所有三角形于各个顶

7、点即可。这个问题是可解的。另外，虽然边图不都是完美图，可以证明二分图对应的边图都是完美图。定理2：二分图对应的边图都是完美图。证明：1、证明二分图对应的边图中没有高于3阶的奇阶洞假设边图中存在高于3阶的奇阶洞，则易知这些顶点在原图中对应的边构成一个奇阶环，这与二分图中没有奇阶环矛盾。2、证明二分图对应的边图中没有高于3阶的奇阶井假设边图中存在2K＋1阶井，（K≥2，K∈N*）。若K＝2，则该5阶井就是一个5阶环，由1得矛盾；若K＝3，设该7阶井的顶点依次为1..7，从1开始依次构造原图，可以发现前5条边

8、加入满足条件的本质不同的方式只有一种，而第6条边无法加入，矛盾（如图）。这个性质对任意边图都成立。若K≥4，设该7阶井的顶点依次为1..2K＋1，则易知顶点集{1,3,5,7,…2K-1}与{2,4,6,8…2K}在边图中分别构成两个顶点数不少于4的团。由于边图中的团在原图中只有两种情况，这里三角形显然不可能，因此必定是交于同一点的边集。由因为边图中顶点1、2见无边，因此这两个团的公共点A、B不重合。又边图中顶点2K＋1与顶点2，3，4，5都相邻，因此原图中该边只可能连接顶点A和B。于是该边与边1相邻，

9、这与边图中这两个顶点见无边矛盾。这个性质对任意边图都成立。综上所述，二分图的边图中没有高于3阶的奇阶井。由1、2，根据强完美图猜想，二分图边图是完美图。证毕。▊**4．圆弧图圆弧图是另一类相交图，可以看作区间图的推广。定义3：图G是圆弧图，当且仅当G是一个圆周上若干圆弧的相交图。图3是一个圆弧图的例子。可见这个圆弧图是一个5阶洞，因此圆弧图不一定是完美图。4．1．圆弧图的结论ò判定：可以在线形时间O(n+m)时间内判定，具体见[HBH90,DHH96]。ò染色：圆弧图的染色与一般图一样是NP问题。[GJ

10、MP78]ò团：这是一个可解的问题，见[Gav74]。5．T－区间图。定义4：一个图G是T－区间图，当且仅当它是元素个数不多于T的区间的集合构成的相交图。图4是一个2－区间图的例子，这个图是一个5阶洞，因此当T≥2时T－区间图不一定是完美图。5．1．T－区间图的结论ò与其他类型图的关系¢－由定义可知1－区间图就是区间图¢－树是2－区间图¢－边图是2－区间图¢－平面图是3－区间图⎡⎤(∆+1)/2¢－任意图G都是区间图，其中Δ是G中度最大顶点