弦图与区间图-陈丹琦

清华大学陈丹琦ChordalGraphandIntervalGraph弦图与区间图2009年1月全国信息学冬令营讲稿图的基本概念子图(subgraph)图为图G的子图(,),,GVEVVEE(,)GVE2009年1月全国信息学冬令营讲稿图的基本概念诱导子图(inducedsubgraph)图称为图G的诱导子图(,)GVE(,),,{(,)|,,(,)}GVEVVEuvuvVuvE2009年1月全国信息学冬令营讲稿图的基本概念团(clique)图G的一个子图，为关于的完全图。(,)GVEVG2009年1月全国信息学冬令营讲稿图的基本概念团(clique)图G的一个子图，为关于的完全图。(,)GVEVG极大团(maximalclique)一个团是极大团当它不是其它团的子集。2009年1月全国信息学冬令营讲稿图的基本概念团(clique)图G的一个子图，为关于的完全图。(,)GVEVG极大团(maximalclique)一个团是极大团当它不是其它团的子集。最大团(maximumclique)点数最多的团。()G团数2009年1月全国信息学冬令营讲稿图的基本概念最小染色(minimumcoloring)用最少的颜色给点染色使相邻点颜色不同。()G色数2009年1月全国信息学冬令营讲稿图的基本概念最大独立集(maximumindependentset)最大的一个点的子集使任何两个点不相邻。()G2009年1月全国信息学冬令营讲稿图的基本概念最小团覆盖(minimumcliquecover)用最少个数的团覆盖所有的点。()G2009年1月全国信息学冬令营讲稿图的基本概念()()GG团数≤色数2009年1月全国信息学冬令营讲稿图的基本概念()()GG团数≤色数()()GG最大独立集数≤最小团覆盖数2009年1月全国信息学冬令营讲稿弦图的概念弦(chord)：连接环中不相邻的两个点的边。Chord2009年1月全国信息学冬令营讲稿弦图的概念弦(chord)：连接环中不相邻的两个点的边。弦图(chordalgraph)：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。2009年1月全国信息学冬令营讲稿弦图的概念弦(chord)：连接环中不相邻的两个点的边。弦图(chordalgraph)：一个无向图称为弦图当图中任意长度大于3的环都至少有一个弦。弦图的每一个诱导子图一定是弦图。弦图的任一个诱导子图不同构于Cn(n3)2009年1月全国信息学冬令营讲稿弦图的判定[例题]Zju1015Fishingnet给定一个无向图，判定它是否为弦图。单纯点(simplicialvertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v}+N(v)的诱导子图为一个团。2009年1月全国信息学冬令营讲稿弦图的判定[例题]Zju1015Fishingnet给定一个无向图，判定它是否为弦图。单纯点(simplicialvertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v}+N(v)的诱导子图为一个团。2009年1月全国信息学冬令营讲稿弦图的判定[例题]Zju1015Fishingnet给定一个无向图，判定它是否为弦图。单纯点(simplicialvertex)：设N(v)表示与点v相邻的点集。一个点称为单纯点当{v}+N(v)的诱导子图为一个团。引理：任何一个弦图都至少有一个单纯点，不是完全图的弦图至少有两个不相邻的单纯点。2009年1月全国信息学冬令营讲稿弦图的判定完美消除序列(perfecteliminationordering)定义：一个点的序列(每个点出现且恰好出现一次)v1,v2,…,vn满足vi在{vi,vi+1,…,vn}的诱导子图中为一个单纯点。v6v5v4v3v2v12009年1月全国信息学冬令营讲稿弦图的判定完美消除序列(perfecteliminationordering)定义：一个点的序列(每个点出现且恰好出现一次)v1,v2,…,vn满足vi在{vi,vi+1,…,vn}的诱导子图中为一个单纯点。v6v5v4v3v2v12009年1月全国信息学冬令营讲稿弦图的判定定理：一个无向图是弦图当且仅当它有一个完美消除序列。2009年1月全国信息学冬令营讲稿弦图的判定定理：一个无向图是弦图当且仅当它有一个完美消除序列。证明：充分性由引理知任何一个弦图都至少有一个单纯点以及弦图的诱导子图都是弦图。可以使用数学归纳法假设当点数n的弦图一定有完美消除序列，那么点数为n的弦图的完美消除序列可以由一个单纯点加上剩余点的诱导子图的完美消除序列得到。2009年1月全国信息学冬令营讲稿弦图的判定定理：一个无向图是弦图当且仅当它有一个完美消除序列。证明：必要性反证若无向图存在一个长度3的无弦环，不妨设环中在完美消除序列中出现在最前面的点为v，设环中v与v1,v2相连，根据完美消除序列的性质知v1,v2相连，与环无弦矛盾。所以无向图为弦图。2009年1月全国信息学冬令营讲稿求完美消除序列最朴素的算法：每次找一个单纯点v，加入到完美消除序列中。将v以及相关的边从图中删掉。重复以上过程直到所有点都被删除(图为弦图，得到了完美序列)或不存在单纯点v(图不是弦图)。2009年1月全国信息学冬令营讲稿求完美消除序列最朴素的算法：每次找一个单纯点v，加入到完美消除序列中。将v以及相关的边从图中删掉。重复以上过程直到所有点都被删除(图为弦图，得到了完美序列)或不存在单纯点v(图不是弦图)。时间复杂度??O(n4)2009年1月全国信息学冬令营讲稿求完美消除序列最朴素的算法：每次找一个单纯点v，加入到完美消除序列中。将v以及相关的边从图中删掉。重复以上过程直到所有点都被删除(图为弦图，得到了完美序列)或不存在单纯点v(图不是弦图)。时间复杂度??O(n4)下面介绍两个求完美消除序列O(m+n)的算法。2009年1月全国信息学冬令营讲稿LexBFS算法字典序广度优先搜索(LexicographicBFS)从n到1的顺序依次给点标号。每个点维护一个list记录与它相邻的已标号点的标号，list中的标号按照按从大到小排序。每次选择list字典序最大的未标号点标号。2009年1月全国信息学冬令营讲稿LexBFS算法LexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。2009年1月全国信息学冬令营讲稿LexBFS算法vnLexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。2009年1月全国信息学冬令营讲稿LexBFS算法vnLexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。2009年1月全国信息学冬令营讲稿LexBFS算法vnvn-1vnLexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。2009年1月全国信息学冬令营讲稿LexBFS算法vnvn-1vnLexBFS与BFS不同在于每次扩展的节点加了特殊的顺序。2009年1月全国信息学冬令营讲稿LexBFS算法算法实现?2009年1月全国信息学冬令营讲稿LexBFS算法算法实现更新一个点的list最多新建一个桶。任何时候桶的数目不超过n。2009年1月全国信息学冬令营讲稿LexBFS算法算法实现O(m+n)!!!更新一个点的list最多新建一个桶。任何时候桶的数目不超过n。2009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。2009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=700100012009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=600200112009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=501200212009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=402201212009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=312202212009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=222202212009年1月全国信息学冬令营讲稿MCS算法最大势算法MaximumCardinalitySearch从n到1的顺序依次给点标号(标号为i的点出现在完美消除序列的第i个)。设label[i]表示第i个点与多少个已标号的点相邻，每次选择label[i]最大的未标号的点进行标号。i=122202212009年1月全国信息学冬令营讲稿MCS算法2009年1月全国信息学冬令营讲稿MCS算法算法实现?2009年1月全国信息学冬令营讲稿MCS算法算法实现0122009年1月全国信息学冬令营讲稿MCS算法算法实现012O(m+n)!!!2009年1月全国信息学冬令营讲稿弦图的判定判断一个序列是否为完美消除序列2009年1月全国信息学冬令营讲稿弦图的判定判断一个序列是否为完美消除序列朴素的算法依次判断{vi+1,…,vn}中所有与vi相邻的点是否构成了一个团。时间复杂度:2((deg()))()OvOmn2009年1月全国信息学冬令营讲稿弦图的判定判断一个序列是否为完美消除序列优化后的算法设{vi+1,…,vn}中所有与vi相邻的点依次为vj1,…,vjk。只需判断vj1是否与vj2,…,vjk相邻即可。时间复杂度:O(m+n)2009年1月全国信息学冬令营讲稿弦图的判定判断一个序列是否为完美消除序列优化后的算法设{vi+1,…,vn}中所有与vi相邻的点依次为vj1,…,vjk。只需判断vj1是否与vj2,…,vjk相邻即可。时间复杂度:O(m+n)弦图判定问题可以在O(m+n)的时间内解决。2009年1月全国信息学冬令营讲稿设第i个点在弦图的完美消除序列第p(i)个。令N(v)={w|w与v相邻且p(w)p(v)}弦图的极大团一定是的形式。证明：设点集V的诱导子图为弦图的极大团，设v为V中p(i)值最小的点即出现在完美消除序列中最前面的点。由于为一个团，V为极大团所以。弦图的极大团()v