区间图、弦图和完美图.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.58M 资料格式：pdf 举报版权申诉

luoyupeng-7241063-16359647317587744440.pdf-第1页.png

第1页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第2页.png

第2页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第3页.png

第3页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第4页.png

第4页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第5页.png

第5页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第6页.png

第6页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第7页.png

第7页 / 共46页

luoyupeng-7241063-16359647317587744440.pdf-第8页.png

第8页 / 共46页

文本预览

区间图、弦图和完美图介绍

内容介绍 • 在本讲中将主要介绍 – 区间图(interval graph) – 区间图上的色数(chromatic number)和最大团问题(maximum clique) – 完美消除序列(perfect elimination order) – 弦图(chordal graph)及其判定 – 区间图的判定 – 完美图(perfect graph)

区间图 – POJ1083 • [POJ1083] Moving Tables 一个公司有400个房间，布局如上图所示。编号为奇数的房间在背面，编号为偶数的房间在南面，中间被一条走廊隔开。现在公司要将某些桌子从一个房间移动到另一个房间。走廊很窄，如果两张桌子需要经过同一段走廊的话，那么它们不能同时移动。每移动一张桌子需要10分钟。问最少需要多久才能将所有桌子移动完毕。

区间图 – POJ1083 Moving： 2 -> 4 5 ->14 12 -> 10 6 -> 1 2 4 5 14 6 1 12 10 求一般图的色数是NP难问题！

区间图 – 定义 • 一个区间是有两个端点的线段，端点可以是开的或闭的。给定一些区间，可以定义一个相交图。 • 定义1：给定一些区间，定义一个相交图的每个顶点v代表一个区间Iv, 顶点(v,w)间有边，当且仅当Iv交Iw非空。 • 定义2：一个图G是区间图，如果它是若干区间的相交图。

区间图 – 例 • 区间图的例子 • 不是区间图的例子

区间图 – 顶点排序 • 定理1：开区间、闭区间、半开闭区间对应的区间图是等价的。 • 证明思路：由于区间在连续的实数轴上，我们可以对区间做小量伸缩而不影响相交情况

区间图 – 顶点排序 • 推论1：任何区间图G都存在一个没有重点的区间表示 • 于是我们可以将G的顶点按其代表区间的左端点排序，称之为区间图G顶点的自然排序

分享到：

赞收藏

资料库

区间图、弦图和完美图.pdf

相关推荐

开发技术

热门标签

最新资料