图论排队论算法

第一部分：第一部分：区间图、弦图、相似图、完美本书英文版共29讲，第一部分共12讲，系译者学习的同时为备以后查阅复习之便作的1210（包括证明79121．概。—HARD2．一些图的分graphs：ersectiongraph表示，那么1．概。—HARD2．一些图的分graphs：ersectiongraph表示，那么同时学习各种相关的图，例如弦图和完美图。这部分的主要参考是[Gol80]树（Trees：一个图是一颗树，当且仅当它是连通的，并且没有环partialk-trees.这部分的主要参考是[Bod93]平面图（Planargraphs：一个图如果能画在二维平面上，且各边没有交点，则该图lanargraphsseries-parallelgraphs（混联图。这部分的主要参考是[NC88]3．一些问Set立集问题能够在O（N＋M）时间内解决，同时在树上可NP最大割umCut)G＝（V，E）A＋BAB4．4．典型问给定一个问题P和一类CC上解P的复杂度是多少C上会变得简单些（复杂度低些）？CNP难题？C这类图？CC新的性质。GCC的“接近程度”是多少？GCG’G’PG’G的解（或近似解NP1．介后学习怎样判定一个图是否是区间图（同时看到一些不是区间图的图2．定个相交图（ersectiongr1．介后学习怎样判定一个图是否是区间图（同时看到一些不是区间图的图2．定个相交图（ersectiongraph。定义1：给定一些区间，定义一个相交图的每个顶点v代表一个区间Iv,顶点(v,w)间有IvIw非空。2GS中的边组成的子图。G3．区间考古学PDF-PCk（k>=4来看一下C4（见图3，假设它是区间图。由于a与b,c相联，它们对应的区间必db,cd对应的区间（d）b,caa,d。34Ckgfa。34Ckgfa。（见图5，对称的情形被忽略了4．定1的证231稍微拉近一段小距离（6I={I1,I2,…,In}Ii={Si,Fi}们再定义I’={I1’,I2’,…,In’},其中Ii={Si’,Fs’}两端都是闭的，其中{Si’,Fi’}如下取值1,12中有三种可能。如这端都是闭，那么操作后它们的交集长度将增加；如这两端都是开的，操2度将减少/2们再定义I’={I1’,I2’,…,In’},其中Ii={Si’,Fs’}两端都是闭的，其中{Si’,Fi’}如下取值1,12中有三种可能。如这端都是闭，那么操作后它们的交集长度将增加；如这两端都是开的，操2度将减少/22×，如果令<=1/3*（2只要证明充分性的否命题，情况与充分性类似，只要满足<=1/3*（两靠近端点的距离）（9）111▋1向，即从左往右（>Succ（Vi）＝{Vj|（Vi，Vj）E}。|Pred（Vi）|Vi（Vi）|Vi注意：区间图中所有Pred（Vi）中的元素对应的区间两两相交。这说明（Vi）是一个团NP1．介[e5kn[76。operationresearch识别等NP1．介[e5kn[76。operationresearch识别等[Oga86]让2．图的染2GX（G）GKK22－SAT（K>=3）NP31：3NP（NP难题，NP定义4：NAE－3－SAT问题：给定一个命题集合U和一个由U及非U的若干三元子集组成的集合C，是否存在一个U中变量的取值方法使C中的每个子集至少包含一个TRUEFALSENP难题[GJ79,p.259]1r的三条边。R，T，FRrT（TRUE接下来NAE－3－SATG3必要性：如果一个图能够3染接下来NAE－3－SATG3必要性：如果一个图能够3染色，则内点必为TF色，代表这个命题的真假，对于余两种颜色，必定不是可行的反色方法NAE－3－SAT问题的要求。3NAE－3－SATNP3NP1▋3．图染色的一个贪心算NP（能用贪心算法进行一种可行染色（Gmax{Vi的入度|种颜色（当然这个结果很不理想。注意顶点的顺序直接影响着颜色数的多少（20034．染色算法最佳的条，）法（见第二讲，Vi*是一个大小为（Vi*的入度＋1）染色需要（Vi*的入度＋1）25：一个顶点序列{V1..Vn}iPred（Vi）是一个团，那么这种序列3GX（，Vi*是一个大小为（Vi*的入度＋1）染色需要（Vi*的入度＋1）25：一个顶点序列{V1..Vn}iPred（Vi）是一个团，那么这种序列3GX（G注：1 225．最大团问定义6：一个图的最大团数W（G）是4W（G）NP完整的证明可参考[GJ79,p.53-56]IGG－I中GW（G2看到Vi*是一个大小为|Pred（Vi*）|+1的团,因此>=|Pred（Vi*）|+1G，X（G）>=W（G为K的团至少需要K2的证明表明X（G）＝|Pred（Vi*）|+1,i*）|+1＝X（GG，X（G）＝W（GXG，X（G）＝W（G5。1．介NP能出色地将这些问题在多项式（而且经常是线性）LornaStewart。学2．定一个图GK各顶点的独立集称为。1．介NP能出色地将这些问题在多项式（而且经常是线性）LornaStewart。学2．定一个图GK各顶点的独立集称为G。3．寻找独立集的一个可行算G以及一个顶点序列{V1..Vn}（unocd所示的图G定理1：如果{V1..Vn}是一个完美消除序列，那么以上贪心算法对与定理1：如果{V1..Vn}是一个完美消除序列，那么以上贪心算法对与顶点序列{Vn..V1}可证明很容易得知完美消除序列的逆序具有如下性质对于每个 iijijiiVi1M＝（S，I，SI▋NP难题在区间图上能够用线性或多项式时间解决，这些NP难题，例如货郎问题：给定一些城市即之间的距离，要求找出一条找包含所有顶点的最短路。由于可以在任意两个城市间行走，该图是一个完全图Kn。显Kn（不包括边权）是一个区间图4．区间图的补一个区间，但两个顶点之间有边，当且仅当对应的区间不相交（见图2G（VE （VDE Vu到vIuIv1G＝（V，E）的一个定向图（又称竞赛图）E中的每条边（u,v）满足对所有 V，且u到v有边，v到w有边，则u到满足对所有 V，且u到v有边，v到w有边，则u到w有边，则称为具有传是边无环可传递的。因此区间图的补图（不带方向）3G，它的补图是伴相似图，但却不是区间图（C4。XY5．弦（K>=4（4（5感2GG的相邻点C（621．介2．弦图与完美消除序GG1GG1．介2．弦图与完美消除序GG1GGGN使用归纳法：1N＝1GN<=K（K>=1，GG不是完全图，可以找到边EG[V－S]GV－S诱导的子图。SV－{a,b}bG[V－S]AB中，Sb是孤立点Sa，b相邻的顶点集合（G－SABAGA＋SSA2：GA＋SGA＋S|GA＋S||G|＋Sx，x，）E2B：xyS1：x与yA、BxAxS2B：xyS1：x与yA、BxAxS 1xB，yBAABx，y（1Ax到y，Bxy是一个4ax＝aybx＝by44的环上都有弦（连接不相邻顶点的边AGG2B综上所述，AB中也存在一个单纯点。显然这两个点不相邻。1得证。▋SG是一个弦图，HGV（G，EE（GH中的环显然也成立。定理0得证。▋推论2：每个弦图都有 N1：N＝1，显然成立2：N＝K－1，K>=2N＝KGVk，G[V－Vk]也是弦图得序列{V1..Vt,Vk}G2得证。▋2的证明暗示了一种迭代地寻找完美消除序列的方法。FulkersonGross1965G得序列{V1..Vt,Vk}G2得证。▋2的证明暗示了一种迭代地寻找完美消除序列的方法。FulkersonGross1965GG33．算了解在O（n+m）时间内寻找完美消除序列的具体算法3．1．最大势算法Tarjan197613．2．字典序广度优先搜索（LexicographicalLueker、Rose、Tarjan1976年提出。算法将顶点标号，然后选择字典序LaLbLaLb4．算法过程实色顶点表示目前选择的顶点。(E文版。4．1．最大势算法KV1..Vk顶点边的数字表示：顶点（该顶点的相邻点中已选择的顶点数每次迭代 只对尚未选择的顶点3．2．字典序广度优先搜索（Lexicographical3．2．字典序广度优先搜索（LexicographicalKMCSBFS都得不到的完美消除序列。这将作为本讲的作业LexBFS1．介LexBFSO（n+m）余线性的时间 LexBFS1．介LexBFSO（n+m）余线性的时间 O（1LexBFS朴素的算法是测试每个顶点的前驱集合是否一个团，这需要O（m+n）的算法2．LexBFS算法的复杂LexBFS 在Vn－1的相邻点之前 。LexBFS与标准BFS的唯一区别是LexBFS给Vn的相邻（3．数据结LexBFS（V）＝lV，LV的标号。Q中不能包含空链表。QAQ3CS（L（V）＝lV，LV的标号。Q中不能包含空链表。QAQ3CS（L（i） 下来。注意：为对于这种数据类型的世纪操作，初始时所有顶点都标号Q了所有顶点。显然这个初始化能在O（n）时间内解决ViS（L（Vi）中删去。S（L（i）ViW：W仍在Q中（WQ中的位置）S（L（W）Q中的位置。S（L（W）Q。S（L（W）S（L（W）。（1）Q（n+mΩ（n但注意只在选择某个顶点W的相邻点时才增长它的标号。因此每个顶点的标号长度与O（n＋m。下面证明这个算法的确找到一个完美消除序列（如果有的话1G＝（V，E）是一个图，{V1..Vn}LexBFS算法得出的序列（Vn择的G是弦图，则{Vn..V1}Vj在完美消除序列（假设是）Vi（4）Vi择的G是弦图，则{Vn..V1}Vj在完美消除序列（假设是）Vi（4）ViVjLexBFSV1Vjj邻 ViV1ViV1L（V1）L（V1Vk，k>j，VkViV1注意边（Vj，Vk）不会存在，因为如果有这条边，G4Vk，VjG。小结一 的证明。Vi的标号包含k但Vj的标号不包含。那LexBFS算法中在Vi之前选择Vj呢？则一定存在另一个Vk之前的顶点与Vj相邻但Vk（后者比较容易解决，只要用弦图的性质可以证明那个点与V1又一次重复论点：为什么Vk在Vj 6：V11▋4．检验完美消除序1G是弦图，LexBFSLexBFSO（n+▋4．检验完美消除序1G是弦图，LexBFSLexBFSO（n+mVUVVUU7检验序列{A，D，B，C，E}，这不是完美消除序列。算法运行如下第一轮：Pred（E）＝{B，C，D}，U＝C，Test（C）＝{B，D}。由于第二轮：Pred（C）＝{A，B，D}，U＝B，Test（B）＝{A，D}。由于第二轮：Pred（C）＝{A，B，D}，U＝B，Test（B）＝{A，D}。由于{B，D}，C第三轮：Pred（B）＝{A，D}，U＝D，Test（D）＝{A}。由于Test（B）＝{A，D}，B与它们都相邻，未发现错误，继续。第四轮：Pred（D）＝，TestTest（D）＝{A}D相邻，因此返回FALSE1：这个算法也可以从前向后进行，可能更便于理解。24行有个错误：Pred（Vj）Pred（Vi）。（Vj）WVj都是某个顶点Vi的前驱。由于WPred（Vi）Vi的前驱集V1..Vn不是完美消除序列。另外，假设V1..Vn不是完美消除序列，但算法却返回TRUE。令I为满足以下条件的最小值：存在Vj、Vk（j<k）Vi的两个前驱，它们不相邻UVi最后的前驱。检Vi时，UViVjU（ALSE时 会发现VkTest（U），但VkPred（U），算法将返回 。定理|V||Adj(v)||Test(v)每个顶点V，算法只会将Pred（V）加入到某一个Test（U）中去即|Test(v)||Deg(v)O（n+mLexBFS。还将给 1．介满足（Vi，Vj）ETiTj。还将给 1．介满足（Vi，Vj）ETiTj（集的相交T1..TnV＝{V1..Vn}，E＝{ViVj|TiTj2T那么G＝（V，E）称何T1..TnGG’GTi’，Tj’，ijeeTi’，eTj’注意引理2的否命题是错的，因 可以将定义2如下描述T1..Tn。令V＝{V1..Vn}，E＝{ViVj|TiTj定义4：给定一棵树T(T}G＝（V，E）45N134TT3．N134TT3．定1的证相交是顶点相交的情形（2的情形5A1AiAj；都有UAA1AAyy集成立，考虑这样的一种情况：T1，T2，T3TV12V13P1，P1T1P2V12V23，T3P3P23P13TV12、V23、V133T。首先证明 集形成的相交图都是弦图T对|T||T|＝1时，TTi＝T，i=1..n|T|P2V12V23，T3P3P23P13TV12、V23、V133T。首先证明 集形成的相交图都是弦图T对|T||T|＝1时，TTi＝T，i=1..n|T|2时，T含有一个叶节点V。有两种可能。如果没 恰在V相交，那VTTiVVVTnTnVTn纳假设，TVTn下 证明每个弦图都能表示为一T。 PTPQ与边（P，Q）Vi4．对弦图的最后补充和总6GSSG－S中这两个顶点不连通。证明：假设图G不是弦图，则G一定存在长度大于4的无弦环C。取C中任意两个不相邻顶点A，B，取A、B的一个极小分离集（显然是存在的么这个集合一定包含C中的两个不相邻的顶点（A，B之间仍然连通，即不是一个团。即证。▋[RTL76,TY84]区间图能够性时间内判定弦图是如此5．相似的（注意原无向图可能有员X，Y，Z，XY，YZXZ，（Golumbic给出了一个用线性时间判定相似图的算法[Gol80]G是区间图，GGolumbic给出了一个用线性时间判定相似图的算法[Gol80]G是区间图，G6．相似图的顶点染P是一个部分序中的一条有向边，则由传递性，PPG性时间内求出W（G）与（G）的算法基础定义顶点上的函数H：H（V）＝1＋MAX（H（W）|WVH（V）＝1（由于没有环，这种定义是唯一确定的。在将顶点拓扑排序后，H可VWH（W）H（V）＋1I，HI集一个独立集。令KHH（V1KKW（GＷ（GX（G）＝K＝W（G定理8：在一个部分序中，X（G）与W（G）的值（包括一个最优染色方案和一个最大团NPNP并1．介GG的补图是相似图，GNP4NPNP并1．介GG的补图是相似图，GNP4一些算（DAGHKK（图2）H同 就用K中颜色对顶点染色，易知W（Ｇ）＝X（G）＝K2．2WV1..Vm（VmGV1..VnC（V）VVC（V）VV1：这个算法确实找到了权最大团。K2，由于定向具有传递性，Vi1…Vik－1的权最大团（否则那个权最大团替换Vi1…Vik－1，加上Vi将形成一个权更大的团C（ik－1（i＋（ik－12．3HKH任（1定义（2P是一个部分序，P上的一个反链是一个两两不可比的顶点集。Dilworth1950，这里暂不加证明地使用：P（3K（G不妨加一个限制：团覆盖中的各个团两两没有交集。显然这不会改变K（G）的（1I（G）＝K（GW（G）＝X（G定理，GI（G）＝K（G。▊（3I’（G。（2C’（G（（G’＝（（G’＝（G’（G’＝I（GGG’中存在一个包含该路径上各点的团，反之亦成立（利用完C’（G）＝K（GI’（G）＝C’（GB（GC（G＝|V|－（G（1＝|V|－B（GM（G）＝B（G对于部分序G，为求I（G（即I’（G）C’（G（K（G）C’（G）10，上限都2．4NP（PDF文件3．部分序的尺每个部分序P都可以扩充成全序（或称拓扑序。令L（P）为P的所有全序组成的集。L（P）L0PIlL0lP，P的最小实现PD（P。分2aa可以用O（n）的空间表示一个全序，因可以用O（D*n）的空间表示一个D 都是相似图则D（P）2 都是相似图则D（P）2D（P）＝D（Q4．再谈区间（1）G（2）G3G 列{j|j{1..k}，vCj}（1）（2： 已知这个命题成立（3）（1I（V）＝[Min{j|VCi}，Max{j|VCi}]。由（3）I（V）＝[A，B]VCjj[A，B]。I（VjI（U）I（V，U、VCj中，因此（U，V）G。（2）（3：H，V（H）G中所有极大团。HC1C2UWUC1，WC22：H5G（A，B1（B2，C）具有传递性，可以推知（A，C） B1B2 会有边 。另外显然不，于是有（A，C）G（G是无向图 。于是有（B1，C）G。同理有（A，B2）G，（A，C，B1，B23：HHHC1C2（6（A，C，B1，B23：HHHC1C2（6。假设（A1，A2）和 ，这里A1，B1C1；A2，B2C2。显然A1B1（ A2B2则由传递性由 （A1，B1，A2，B2，HC1..Cm（3（3对于所有的WCj，中U与W间不会有边否则 CkCjWUCiCj之前。于是在G中U与W之间有边。由于W的任意性，U与Cj中任意顶点在G中都相邻，因为UCj，所以Cj不是极大团， （1）（3件（3。对于证明中涉及的图H，不妨称它为极大团生成图111．介E文。区间111．介E文。区间图的性PDF文件。区间图的判3．1NP2：有NN证明：令G是一个弦图，σ是G的一个完美消除序列。对所有的V，{V}Pred{V}是一个N个。证明每个极大团都是这种形式的。MGM{VPred{V}，VM1：相似图的极大团数是什么数量级的？O（N^N）有一个Vi的前驱不是Vj的前驱。这个结论的正确性很容易得知，这里不再证明。实践M（V，表示点的前驱都是VUUFALSE了这表明可以使用与判定完美消除序列类似的算法来获得所有的极大团，这一步用时（n+3STEP1必须在执3．2这表明可以使用与判定完美消除序列类似的算法来获得所有的极大团，这一步用时（n+3STEP1必须在执3．213．31G是一个图，AGAGG13．3．1C1={V1,V2,V3},C2={V2,V3,V4},C3={V4,V5}1C1、C2、C33．4．PQ1XXL，求X的一个重排П（X，满足对ILI中的元素在П中是连续的1976年，BoothLoeker提出了一PQ树的数据结构来解决这个问PQ树的各个叶节点，表示一个重排П（X。PQ树的节点有两种类型：Q类型，用矩形标识，表示反序；P类型，用圆形标识，表示它的例如以下的PQ3．3．5中PQ1．介NP继BoothPQPQPQ树（定义见上讲）区间图的判XL是PQPQ树的叶节PQ1．介NP继BoothPQPQPQ树（定义见上讲）区间图的判XL是PQPQ树的叶节续性约束集，L＝{Iv|vV}，IvL（PQPQPQ122Type（V）PQXP、Q节点是等价的叶节点都是不染色的，半黑半白表示叶节点中染色与不染色的叶节点都存在，用CL表示。 的来源，与PQ树本身无关。CL（X）＝X节点所有子节点，由于可翻1AXXKSolve（K，yp（K，2SolvePQ1CSolve的目标。 首先扫描 的颜色，显然最多只能有1个半黑半K2AXKSolve（K，ype（K，2XXKSolve（K，yp（K，2SolvePQ1CSolve的目标。 首先扫描 的颜色，显然最多只能有1个半黑半K2AXKSolve（K，ype（K，2B3,PXPX时间；对于每个约束，染色（包括内节点）O（N，递归求解时每个节点至多操作一O（N。因此总复O（NT 所有可行的极大团序列4以上是第一个用线性时间解决区间图判定的算法。KorteMohring之后提出了一个建立在改进PQ树基础上的算法；HsuMaPQ树的算法。Habib、Paul、Vincent的LexBFS间图的方法；Corneil、OlariuStrwart用五次LexBFS算法平判定了区间图，每次使用51CCC中。例如，区W（G）＝X（GW（H）＝X（H由定义可知完美图具有遗传性质。另外，如果一类图C具有遗传性质，且C中的任意图G都有W（G）＝X（G，那么C中的所有图都是完美图。这表明区间图、弦图、相似图都（IK且对于G的任意诱导子图H，（（G）＝W（G（将每个团中的元同的团染不同的颜顶点不相邻，即（G）X（GGG（G）X（GGGK（GG是伴完美图的充要条件是G1（3**1．介3定**1．介3定3。但是它的任意诱导子图（本身除外）都是完美图。这样的图称为极小非完KKK阶反洞。1：奇阶洞与奇阶反洞都是极小非完美图。（SPGC完美图的性NP问题，而且SPGC成立也是这样。I（GW（GX（G1：均衡矩阵FRn×n关于图G的可行，如果：对一个均衡矩阵MRn×n，令λmax（M）为M的最大的特征根。定义图G的函数Min{λmax(F)|F关于G可行（注：均衡矩阵即关于左上/右下对角线对称的矩阵可以证明对于任何图G，有W（G）θ（G）X（G＝X（G接下来要做的是证明θ函数在有效时间内可以求出。可接下来要做的是证明θ函数在有效时间内可以求出。可以得知θ（G）是一个半确定规划有理数R，满足|R－θ（G）|<ξ。由于G是完美图取ξ<1/2就能准确得到θ（G）的值了知道θ（G）是整数，因此只这 **4．完美图的另一些特一个图G＝（V，E）是分离图，如果V可以分割两个ICI是一个独立集，C2假设π1..NE确地说，(U<V)XOR(π(U)>π(V))为真。3GG4．3GW：VN*TN*W(v)I4是一个T＝6。（K1,6K1,86个顶点。GG是一个极限图，但反之不成立。4．4W（X值等于各个元素权值的和。则有序