数宽及其在图论中的应用答辩

树宽及其在图论中的应用答辩人：导师：答辩时间：一二三四五目录一、研究概述一、研究概述本文的主要工作概括如下1.介绍图的一些基本概念以及图的树分解2.总结在一些不同情况下树宽的定义以及树宽的基本性质，讨论一些特殊图的树宽并予以证明3.给出一些关于树宽在算法方面的应用二、研究背景图论图的树分解树宽的定义研究现状二、研究背景图的树分解图的树分解：设是一个无向简单图（无自环、无重边），则图G的树分解由树和的每一个节点关联的子集构成（称这些子集是树分解的片段）。树和片段集满足以下三个条件:(1)，即全部片段中包含的节点涵盖了图中的所有节点。或者说图中的每一个节点至少属于某一个片段。(2)对图的每一条边，至少存在一个片段包含的两个端点。(3)若是树的三个节点，其中在到的路径上，那么，若的节点属于和，则一定也属于。树的点称为节点（node）或者袋（bag），从而和图G的顶点区分开。若且，则称节点包含顶点。(V,E)GTTttXVtX:tXtTVGGeEtXe123,,ttt2t3tGv1tX3tX2tXtXuVGtuXtXu1t图及图G的树分解Gd,f,gc,f,eb,cd,fa,bbegacfd,TTX,GVE示例二、研究背景GG(T,X)(G)minmax|X|1iiTWGG𝑇𝑊(𝐺)=max𝑖|𝑋𝑖|−1Gd,f,gc,d,fc,f,eb,c,da,b,cagebcfd示例图G最小宽度的树分解(T,X)(G)minmax|X|12iiTW二、研究背景研究现状树分解及树宽的研究现状：由于确定一般图的树宽是NP完全问题，所以没有一个固定的计算公式，因而对于一般图的树宽没有好的算法，所以人们把精力转向了具有特殊结构的图，于是产生了一系列降维、局部约化和分解定理，对于一些已知结构的图来说，他们是行之有效的。所以目前该课题的研究者都研究了许多关于特殊图的树宽以及一些树宽的基本性质。三、一些特殊图的树宽三、一些特殊图的树宽一些特殊图的树宽1.树的树宽2.序列平行图的树宽3.任意连接图和偏k树乘积图的树宽4.r-冠图和n阶方形网格图三、一些特殊图的树宽树定理树的树宽为1证明：对于一个满足定义的图G（即树图G），可以用以下的方法去构建一个树分解，树分解中的与树图G的构造完全一样，每个包含和树图G对应位置的父节点，的根节点对应的包含G的根节点及随意的一个孩子节点，容易验证这样的树分解满足图的树分解的三个条件，且树分解的任意一个都只包含两个节点，因此这个树分解的宽度为1，即。（b）树图的树分解（T,X）（a）树图Gv7,v4v9,v6v8,v6v6,v2v5,v2v4,v1v3,v1v2,v1v1,v2v1v2v5v6v8v9v3v4v7(,)TXTiXTTiXiX()1TWG三、一些特殊图的树宽序列平行图仅包含一条边的图是一个序列平行图。任意给定一个序列平行图，可以通过如下方式得到一个新的序列平行图，即在原图中增加某一条边的平行边，或将原有的某一条边从中间分开，在中间添加一个新的节点。因此所有的序列平行图都可以从最初的一条边通过不断地添加平行边和分割边来产生。证明:（1）因为任何一个序列平行图生成都可以通过增加平行边和分割这两个操作得到。且增加平行边对图的树分解无影响，因为平行边所依附的两个顶点时一样的，所以包含平行边和不包含平行边的序列平行图的树分解是一样的。因此下面只考虑分割操作对于树分解的影响。（2）采用数学归纳法。假设某个序列平行图的树宽为2，则只需要证明该图对于任意一条边采取分割操作后，新得到的序列平行图的树宽还是2。变换三、一些特殊图的树宽（3）假设是图G的一个树分解，树宽为2，为图G的一条边。然后我们对其进行分割操作。即变成两条边，以及一个新的节点，得到一个新的平行序列图G’。（4）设r是原图G的树分解的树上的一个节点，并且。然后构造一个新的树，包含,并且增加一条边，是一个新节点。在树中，令，，且，容易验证满足树分解的三个条件，是图G’的一个树分解。且该树分解的树宽也是2.因为树其他的节点的基数与原来一样，而新增加的节点的基数为3（因为），所以树分解的宽度还是2。证毕。(,)TXuv,uwwvw(,)TXT,ruvX'T'TTrqq'T'ttXX(tV(T)',,qXuvw(',X')T'Tq',,qXuvw(',X')Tr-q变换树分解T'(T',X')图G'树分解T(T,X)图Gb,c,ub,v,uu,v,wa,b,vb,c,ub,v,ua,b,vabcuvvcabuv三、一些特殊图的树宽G||,HVGmVHnnmkTWGHmk三、一些特殊图的树宽r-冠图和n阶方形网格文中给出了图G的r-冠图和一阶网图及n阶方型图的定义，并证明了以下定理：定理1：圈的r-冠图的树宽为2定理2：定理3：定理4：1;2TWFn2,n13;n3,2TWFn2;3TWFn四、树宽在算法中的应用四、树宽在算法中的应用图的树分解算法构造树分解的启发式方法通常有如下两次。第一类是利用消元顺序，即在无向图G中删除节点以及与节点关联的边，同时补充其他边，使得原来的邻节点能构成一个团，通过在图G中逐次消元G中的所有节点，就可以得到一个消元顺序，根据这个顺序便可以构造出图G的一个树分解。第二类是利用割集来构造树分解的启发式算法，即在原始图中寻找一些割集来构造树分解。利用割集递归地分割图，并在分割后的连通分量重构造树分解。四、树宽在算法中的应用问题介绍最小标记树生成法寻找一颗网络生成数，它使用的媒介种类最少，也可以理解为寻找各个边比较相似的生成树。模型化之后就是：给出一个图𝐺=𝑉,𝐸和一个标记函数𝑙𝑒,它对𝐸的边𝑒都打上一个标记，表示该边所对应的通讯渠道的类型。我们的目标就是找出这样的一个生成树，它使用的标记种类是最少的。四、树宽在算法中的应用虽然最小标记生成树问题不存在多项式内的精确算法，但如果我们把核心放在有限制树宽的图上，就会发现问题没有那么难。本文重点研究树宽限制在k下的问题。在我们的问题中，基于n，k两个参数提出了一个关于n的多项式算法。首先给出一个图和常数k，判断是否存在生成树所用的标记不超过k，有则返回该树。MLST算法在调用递归函数时使用了边的压缩。压缩边𝑒𝑢,𝑣就是将𝑢,𝑣合并为一个顶点𝑤，所有原本邻接𝑢,𝑣的边都压缩到𝑤上。一般图上基于搜索树的算法GT四、树宽在算法中的应用在算法中，𝑙𝑇包含了符合要求的生成数所需要的标记，𝑙𝑠包含了可选用的标记。一旦一个标记从𝑙𝑠中删除，表示符合要求的生成树不可能使用这个标记所在的边。如果满足条件的生成树存在，算法返回的是该生成树所有边的集合。我们可以构造子图𝐺𝑇=𝑉,𝑇𝑙𝑇，它的边是由𝑙𝑇中标记所在的边构成。显然，𝐺𝑇是连通的，我们只需要删除环即可得到所需要的生成树。时间复杂度为𝑂𝑝𝑘𝑘𝑛一般图上基于搜索树的算法标记个数比较小的情况四、树宽在算法中的应用首先将该树分解转换为一个良好树分解，这可以简化我们的计算。（良好树分解：树中的任何节点最多有两个孩子）求最小标记生成树可以转换为求一个标记的集合𝑙𝑇⊆𝑙1,𝑙2,…𝑙𝑃。给定图𝐺和宽度为k的良好树分解，对节点𝑖和任何𝑍⊆𝑋𝑖，定义𝑎𝑖𝑍表示在子图𝐺𝑇𝑖中的最小标记集𝑙𝑇⊆𝑙1,𝑙2,…𝑙𝑃元素的个数，并且满足𝑙𝑇∩𝑙𝑖=𝑍。接下来，我们分四种情况讨论：限制树宽上的最小生成树算法标记个数比较大的情况四、树宽在算法中的应用情况1：𝑖没有孩子节点，|𝑋𝑡|=𝑘或𝑘+1，可以得到𝑎𝑖𝑍=𝑍情况2：𝑖有一个孩子节点，且𝑋𝑗⊂𝑋𝑖,|𝑋𝑖|=|𝑋𝑗|+1.设𝑤∈𝑋𝑖,𝑤∉𝑋𝑗，这里分为两种情况：（1）𝑙𝑖=𝑙𝑗，得到𝑎𝑖𝑍=𝑎𝑗𝑍（2）𝑙𝑗⊂𝑙𝑖,我们得到𝑎𝑖𝑍=min𝑎𝑗𝑍−𝑙𝑤+|𝑙𝑤|。情况3：𝑖只有一个孩子节点，而且𝑋𝑖⊂𝑋𝑗,|𝑋𝑖|=|𝑋𝑗|+1。这里也分为两种情况：（1）𝑙𝑖=𝑙𝑗，𝑎𝑖𝑍=𝑎𝑗𝑍依然维持原来的标记组合。（2）𝑙𝑖⊂𝑙𝑗，得到𝑎𝑖𝑍=𝑍∪𝑙𝑤情况4：𝑖有两个节点，可以得到𝑎𝑖𝑍=𝑎𝑗𝑍+𝑎𝑘𝑍−|𝑍|限制树宽上的最小生成树算法标记个数比较大的情况四、树宽在算法中的应用限制树宽上的最小生成树算法标记个数比较大的情况结合以上四种情况的计算方法后，我们可以后序遍历树𝑇，对于树中的每个节点通过它的孩子节点的值来计算𝑎𝑖𝑍.我们采用自底向上的计算顺序，所以计算每个节点的时候，它的所有孩子的目标值都已经算好了。一直到根，而根的𝑎𝑟𝑍就是整个图的最小可标记集的大小。时间复杂度为𝑂2𝑘2+𝑘𝑘𝑛五、研究展望1、图的树宽以及图的一些其他特性之间的联系2、在一些限制条件下一般图的树宽的计算3、图的树分解算法感谢老师的悉心指导！感谢各位评审老师的聆听！谢谢！恳请评委老师批评指正。