购买

¥ 25.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 最新文档-区间图弦图和完美图-PPT精品文档

最新文档-区间图弦图和完美图-PPT精品文档.ppt

最新文档-区间图弦图和完美图-PPT精品文档

精品课件库
2019-06-17 0人阅读 举报 0 0 暂无简介

简介:本文档为《最新文档-区间图弦图和完美图-PPT精品文档ppt》,可适用于职业岗位领域

区间图、弦图和完美图介绍内容介绍在本讲中将主要介绍区间图(intervalgraph)区间图上的色数(chromaticnumber)和最大团问题(maximumclique)完美消除序列(perfecteliminationorder)弦图(chordalgraph)及其判定区间图的判定完美图(perfectgraph)区间图–POJPOJMovingTables一个公司有个房间布局如上图所示。编号为奇数的房间在背面编号为偶数的房间在南面中间被一条走廊隔开。现在公司要将某些桌子从一个房间移动到另一个房间。走廊很窄如果两张桌子需要经过同一段走廊的话那么它们不能同时移动。每移动一张桌子需要分钟。问最少需要多久才能将所有桌子移动完毕。区间图–POJMoving:>>>>求一般图的色数是NP难问题!区间图–定义一个区间是有两个端点的线段端点可以是开的或闭的。给定一些区间可以定义一个相交图。定义:给定一些区间定义一个相交图的每个顶点v代表一个区间Iv,顶点(v,w)间有边当且仅当Iv交Iw非空。定义:一个图G是区间图如果它是若干区间的相交图。区间图–例区间图的例子不是区间图的例子区间图–顶点排序定理:开区间、闭区间、半开闭区间对应的区间图是等价的。证明思路:由于区间在连续的实数轴上我们可以对区间做小量伸缩而不影响相交情况区间图–顶点排序推论:任何区间图G都存在一个没有重点的区间表示于是我们可以将G的顶点按其代表区间的左端点排序称之为区间图G顶点的自然排序区间图–顶点排序区间图–顶点排序定义:Pred(Vi)={Vj|(Vi,Vj)∈E∧j<i}为顶点Vi的前驱{Vi}∪Pred(Vi)是一个团区间图–最小染色算法令v,vvn为顶点的一个自然排序一下算法得到区间图G的一个最小染色完美消除序列定义:一个顶点序列{VVn}如果对任意i满足Pred(Vi)是一个团那么这种序列称为完美消除序列。最大团最大独立集最小覆盖最小团覆盖……弦图定义:如果一个图的任何诱导子图都不是K阶环(K>=)那么该图称为弦图弦图与完美消除序列定理:如果一个图G具有完美消除序列则G是弦图。弦图与完美消除序列定理:图G是弦图当且仅当G具有完美消除序列弦图与完美消除序列定义:如果与顶点V相邻的所有顶点构成一个团则V称为单纯点引理:任何弦图G具有至少一个单纯点。如果G不是完全图那么它至少具有两个不相邻的单纯点。引理:弦图的任何诱导子图都是弦图。弦图与完美消除序列引理:任何弦图G具有至少一个单纯点。如果G不是完全图那么它至少具有两个不相邻的单纯点。弦图与完美消除序列最大势算法(MCS)字典序广度优先搜索(LexicographicalBFS)弦图与完美消除序列LexBFS{A,D,C,B,E,F,G,H,J,K,I,L}弦图的判定LexBFS–O(nm)令Vi是第一个桶中的第一个元素(显然Vi是目前标号最大的一个顶点)。将Vi从桶S(L(Vi))中删去。如果S(L(Vi))已空将它从Q中删去。对于每个Vi的相邻点W:如果W仍在Q中(W尚未选择必须更新它的标号和在Q中的位置)找到S(L(W))以及它在Q中的位置。寻找Q中S(L(W))上一个桶。如果这样的桶不存在,或它不是S(L(W)〇i)在Q中的当前位置建立一个桶S(L(W)〇i)将W从S(L(W))中取出并加入S(L(W)〇i)中如果S(L(W))已空将它删除。将L(W)更新为L(W)〇i。弦图的判定检验–O(nm)弦图的判定ZOJ–FishingNet判断一个图是不是弦图再谈区间图定理:以下命题是等价的:()G是区间图()G是弦图且G是伴相似图(cocomparabilitygraph)。()G的极大团可以连续地编号。即我们可以将它们排为CCk满足对于任何v∈V序列{j|j∈{k}v∈Cj}是连续整数集。再谈区间图定义:一个能够无环且具有传递性地定向的无向图G称为相似图。定理:()>()定理:()>()I(V)=Min{i|V∈Ci}Max{i|V∈Ci}再谈区间图定理()>()令G’是G补图经过无环传递定向后的有向图。构造有向图HV(H)=C,<C,C>∈E(H)存在x∈C,y∈C且<x,y>∈G’再谈区间图定理:H是传递的再谈区间图定理:H是无环的再谈区间图定理:H的一个拓扑排序C,C,…Ck是满足()的一个序列区间图的判定区间图的判定定理:设G是弦图M是G的一个极大团则存在iM={Vi}∪Pred(Vi)定理:{Vi}∪Pred{Vi}是极大团当且仅当对Vi的任何后继Vj至少有一个Vi的前驱不是Vj的前驱。区间图的判定连续性质(consecutiveonesproperty,COPorCP)POJ:判断一个矩阵是否具有CPAnmaij=Vi∈Cj区间图的判定N=S={,}{<,,,>,<,,,>,<,,,>,<,,,>,<,,,>,<,,,>,<,,,><,,,>,<,,,>,<,,,>,<,,,>,<,,,>}S={,}{<,,,>,<,,,>,<,,,>,<,,,>}区间图的判定PQtreegregablepqtreealgorithmandconsecutiveoneshtmljharriscaportfoliocodepqtreePQTreehtml区间图的判定pertinentroot区间图的判定L当前节点是叶子标记为full区间图的判定P当前节点是Pnode,子节点都是full标记为full区间图的判定PPnode,pertinentroot,fullempty增加新的Pnode作为full子节点的父节点及当前节点的子节点(如果只有个full子节点则不增加新的Pnode)区间图的判定PPnode,notpertinentroot,fullempty当前节点标记为partialQnode,增加新的Pnode作为full子节点的父节点及当前节点的子节点,增加新的Pnode作为empty子节点的父节点及当前节点的子节点,区间图的判定PPnode,pertinentroot,partialfullempty区间图的判定PPnode,notpertinentroot,partialfullempty区间图的判定PPnode,pertinentroot,partialfullempty区间图的判定QQnode,allfull区间图的判定QQnode,partial连续fullempty区间图的判定QQnode,partial连续fullempty完美图定义:一个图G是完美图如果W(G)=X(G)且对于G的任意诱导子图H都有W(H)=X(H)。强完美图定理强完美图定理(SPGT)一个图是完美图当且仅当它的任何大于的诱导子图都不是奇阶洞或奇阶反洞

VIP尊享8折文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/46

最新文档-区间图弦图和完美图-PPT精品文档

¥25.0

会员价¥20.0

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利