（应用数学专业论文）门槛图和拟门槛图中的一些优化问题.pdf

摘要 本文主要研究门槛图和拟门槛图的结构特点，并在此基础上解决了这两类图中 的一些优化润题。 第一章中首先研究了门槛图的结构，得出这类图实质上是由一些单点的和或积 得到的。认清这一结构性质后，本章设诗了多项式对闻算法构造嵩了反映 j 槛圈结 构性质的两种图一门槛图的中心树和树形代表咒。然后，利用中心树和树形代表 所反映的门槛图的性质，本章解决了门槛图孛的以下优化问题：( 1 ) 设计多项式时 间算法识别门槛图；( 2 ) 利用中心树找出门槛图的最大团，得到门槛图的最小边割 集是平凡的；( 3 ) 构造树形代表，然后证明了树形代表的时子节点构成原图麴最大 独立子集：( 4 ) 给出门槛图是哈密尔顿图的充要条件；( 5 ) 设计多项式时间算法计 算出门槛图的带宽。 第二章首先构造了拟门槛图的树形代表，同时由构造树形代表的算法来识别拟 门槛图，因为一个图是拟门槛图当且仅当它是某个树形图的导出图，而这个树形图 就是该 1 槛图的树形代表。然厝，由树形代表毒发来构造其孛心树，并在此基础上 解决了拟门槛图中的以下优化问题：( 1 ) 找出拟门槛图的染色数、最大独立子集和 最小团覆盖；( 2 ) 计算拟门槛图的带宽；( 3 ) 分析拟f 了髅图的哈密尔顿性；( 4 ) 设 计多项式时间算法解决拟门槛图的边控问题。 关键词：门槛图；拟门槛图；优化问题 a b s t r a c t i nt h i sp 印e r w em a i n l yd os o m er e s e a r c ho nt h r e s h o l dg r a p h sa n dq u a s i t h r e s h o l d g r a p h s ，s o l v i n gs e v e r a lo p t i m i z a t i o np r o b l e m s o nt h eb a s i so ft h e i rs p e c i a ls 锄c 瓣 i nt h ef i r s tc h a p t e r ，w es t u d yt h es t r u c t u r eo ft h r e s h o l dg r a p h sf i r s t l y ，c o n c l u d i n gt h a t t h i sc l a s so fg r a p hi so b t a i n e df r o ms o m ev e r t i c e sw h i c ha c t a su n i v e r s a lv e r t i c e so r i s o l a t e dv e r t i c e s a f t e rm a s t e r i n gi t ss t r u c t u r e ，w ed e s i g nap o l y n o m i a lt i m ea l g o r i t h mt o c o n s t r u c ti t sc e n t t r e ea n da r b o r e s c e n c er e p r e s e n t a t i o n ，w h i c h w e l lr e f l e c ti t ss t r u c t u r e o n t h i sb a s i s w es o l v ef o l l o w i n go p t i m i z a t i o np r o b l e m so nt h r e s h o l dg r a p h ss u c c e s s f u l l y ：( 1 ) c o n s t r u c t i n gap o l y n o m i a lt i m ea l g o r i t h mt or e c o g n i z eat h r e s h o l dg r a p h ；( 2 ) f i n d i n go u t t h em a x i m u mc l i q u ea n dm i n i m u me d g e c u to fat h r e s h o l dg r a p h ；( 3 ) c o n s t r u c t i n gt h e a r b o r e s c e n c er e p r e s e n t a t i o no fat h r e s h o l dg r a p h ，f i n d i n go u tt h em a x i m u md e p e n d e n t s e t w h i c hi sm a d eu pb ya l l l e a v e so fi t sa r b o r e s c e n c er e p r e s e n t a t i o na n dc o m p u t i n gt n e c h r o m a t i cn u m b e r ；( 4 ) p r e s e n t i n gas u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rat h r e s h o l d g r a p ht ob eh a m i l t o n i a n ；( 5 ) c a l c u l a t i n g t h eb a n d w i d t ho fat h r e s h o l dg r a p hw i t ha p o l y n o m i a lt i m ea l g o r i t h m i nt h es e c o n dc h a p t e r , w e c o n s t r u c tt h ea r b o r e s c e n c er e p r e s e n t a t i o n o ft h e q u a s i t h r e s h o l dg r a p h ；m e a n t i m e ，w ec a nr e c o g n i z eaq u a s i - t h r e s h o l dg r a p h w i t ht h es a m e a l g o r i t h m b e c a u s eag r a p hi s aq u a s i t h r e s h o l dg r a p hi fa n do n l yi fe a c hc o n n e c t e d c o m p o n e n to fi t i st h ei n d u c e dg r a p ho fs o m ea r b o r e s c e n c e t h e n ，w ec o n s t r u c t t h e c e n t t r e eo faq u a s i t h r e s h o l dg r a p ha c c o r d i n gt o i t sa r b o r e s c e n c e ，w h i c hm a k e si t c o n v e n i e n tt os o l v ef o l l o w i n go p t i m i z a t i o np r o b l e m so nq u a s i - t h r e s h o l dg r a p h s ：( 1 ) f i n d i n go u tt h ec h r o m a t i cn u m b e r , t h em a x i m u md e p e n d e n ts e ta n d t h em i n i m u mc l i q u e c o v e r a g eo faq u a s i t h r e s h o l dg r a p h ；( 2 ) c a l c u l a t i n gt h eb a n d w i d t ho faq u a s i - t h r e s h o l d g r a p h ；( 3 ) p r e s e n t i n gac o n d i t i o nf o r aq u a s i t h r e s h o l dg r a p ht ob eh a m i l t o n i a n ；( 4 ) d e s i g n i n gap o l y n o m i a lt i m ea l g o r i t h mt oc a l c u l a t et h ee d g e 。d o m i n a t i n gn u m b e r k e y w o r d ：t h r e s h o l dg r a p h s ；q u a s i t h r e s h o l dg r a p h s ；o p t i m i z a t i o np r o b l e m s 学位论文独创性声明 本人声明，所呈交的学位论文系本人在导师指导下独立完成的研究成果。文中 依法引用他人成果，均已作出明确标注或得到许可。论文内容未包含法律意义上已 属于他人的任何形式的研究成果，也不包含本人已用于其他学位申请的论文或成果。 本人如违反上述声明，愿承担由此引发的一切责任和后果。 论文作者签名： 豫a 钍 日期：c z o 谚年 月日 学位论文知识产权权属声明 本人在导师指导下所完成的学位论文及相关的职务作品，知识产权归属学校。 学校享有以任何方式发表、复制、公开阅览、借阅、以及申请专利等权利。本人离 校后发表或使用学位论文或与该论文直接相关的学术论文或成果时，署名单位仍然 为青岛大学。 本学位论文属于： 保密口，在年解密后适用于本声明。 不保密眦 ( 请在以上方框内打“”) 论文作者签名：泵己、强 导师签名： 诌敢 l ( 本声明的版权归青岛大学所有， 同期：。b 矿年厂月p 同 日期：诽衫月8 臼 未经许可，任何单位及任何个人不得擅自使用) 3 0 雩l 言 引言 图论是研究由曲线连接的点集的理论。它是- - ( 1 起源很早的学科，早在十八世 纪就也现了图论问题。图论中财各类图的研究都有诸多应用，比如最短路问题 1 1 ， 最优延配闻题p i ，遗嘱染色溜题目等都在匿论研究的范畴。对嚣论中一些特殊圈的 研究尤为重要，其中就包括本文所讨论的门槛图和拟门槛图。这两类图在计算机科 学和整数规划中都有瘟黑。 门槛图的概念是由c h v a t a l 和h a m m e r 首先引入的，妇还给出门槛图的量化定 义 2 1 ：无彝单图g = ( 矿，d 称为f l 槛匿当虽仅当存在一个对于顶点的实值赋权l 煮一 个实数t 满足对矿的任意子集s ，s 是独立集当且仅当五( x ) f 。门槛图是一类有 ：蚕 特殊结构性质的图，有必要对这类雷作单独研究。n i k o l o p o u l o s 利用拟门槛图的判 定来识别门槛图p l ；o r t i z z 得出了门槛图的染色指数是的充要条件1 4 l ；l l a 糊e r 找出了门槛图的拉普拉斯谱，在此基础上算得门槛图的支撑树数目i 卯。 融等人首次提出了拱门槛圈这一概念，并研究了这类图昀代数性质。他证鞠了 一个图是拟门槛图当且仅当它的每个连通分支都是某个树形图的导出图p l 。一个门 槛图对应唯一的树形鬻，这个树形图就称为它的树形代表。有了这个充要条件作依 据，给出了一个o ( n 2 ) 时间算法来识别拟门槛圈l 钉。n i k o l o p o u l o s 根据拟门槛图 的结构提出了拟门槛图中心树的概念1 6 1 。构造了拟门槛图的中心树- y 锄等人建立了 一维算法解决了拟门槛毽的识潮阀题掰。 图论中的许多问题在一般圈中都是肝一c 问题，比如团覆盖问题、啥密尔顿性 阍题、染色阍题等等。但门槛圈潮糍门槛圈具有特殊的结构，这就使我们有了解决 这两类图上一些优化问题的可能性。 本文在研究了门槛圆和拟门槛图的缆构性质厝，深入讨论了门槛墨和撅门槛图 中的一些优化问题。比如设计了多项式算法解决了门槛图的识别问题，构造中心树 解决了门槛圈的最大圃问题，构造树形代表解决丁门槛图最大独立子集问题、最小 边割集闯题、染色问题，设计了多项式算法计算如门槛图的带宽，最后判定了门槛 图的哈密尔顿性。把研究门槛图的方法推广到研究拟门槛图上解决了拟门槛图的最 大独立子集麓题、染色阆题、霞覆盖褥题、带宽润题和边控闻题。从而证明了这些 1 毒麓犬学硬士学位论文 问题在这两类图上是p 问题。 本文涉及到的图都为单圈。 2 第一鬻门槛图巾的优位 文题 1 1 门槛图的识别 第一章门槛图中的优化问题 图g 的顶点v 称作通用点。如粜1 ，与g 的其它顶点都相邻：顶点1 ，称作孤立点， 如果v 与g 的其它任意顶点都不相邻。我们递归地定义门槛图如下： 定义1 1 1 置。是门槛图；在门槛图中加入通用点或孤立点还是门槛图。 定理1 。1 1 网个图是门槛圈当且仅娄它是只一f r e e ，幺一f r e e , j 至2 k 2 - 加寥昀。 如果把与顶点工相邻的所有点的集合记为 必x ) ，o ) u x 记为m x 】，还可以得 到以下定理： 定理1 。1 2 图g = ( 以e ) 是门槛图当且仅当 ( 口 【张鳓咐) 篓m 面对v a , b 氐矿。 证明：赣# 瓣如果存在两点x , y 使褥蠢，t ，葶职班葶g l f x 篷t g 艇硝， 则会出现如图1 1 所示的凹种情况 0 二二u 二二目二 盈1 1 ( a ) 为2 k z ，( b ) 和( e ) 为只，( d ) 为q 。无论出现那种情况都与它是门槛图矛盾。 - 一如果一个图g 满足对v a , b 吒都有( 口) 即】，或( 6 ) g 【砩那么它就是 p 4 - f r e e ，g 一触，置强：一多铭的t 就是门槛图。 定义1 1 2a 、b 是两个互不相交的图，g 鬣a + b 叫做a 和露的和，如果 以g ) = v ( a ) u v ( b ) ，取回= e ( a ) u 职功。g = 彳曾叫做a 和君的积，如果它由 a + b 再加上边( 鸽6 ) ( v a k z ) 。锄以骞) ) 得到。 由定义1 1 2 得疋= 飘9 2 岛，石= 霸十如+ + ， 如果 3 葶 工 l p o，；舂 k ， “ o，舂 8 茹 青繇大学硬士学位论文 矿( k ) = 矿( 两= 霸，g ：， ，筒记为邑黧譬一，石= n g 。 定义i 1 3 设c 是图g 的一个豳，若不存在其它团能包含c ，赠e 称秀g 的极 大团。包含顶点数最多的极大团称为最大团。 定义1 1 4 边他6 ) g 联g ) ，如果有m 刃= 研酗，鼢边“研称为自由边；如果 考m 硼c 研6 嫩6 】cm 胡，则边( 岛幻称为半自由边。 由门槛图的定义我们可以得出：每一个门槛图都可经由一个单点添加孤立点或 通用点褥到，根据这一性质，我们设计下西这个算法可以识别门槛图： 算法1 1 1 门槛图的识剐算法： ( 1 ) 一个不连通图如果有多于一个不是孤立点的连遁分支，则它一定不是门槛图，1 ( 2 ) 对一个连通图，首先检查它是否有通用点，如果没有。剿它一定不是门槛圈； 如果有，把这些点的集合记为c e n t ( g ) 。 ( 3 ) 对g c e n t ( g ) 重复( 1 ) 、( 2 ) 两步操作。 鲡此下去，直到剩下一个萄以识别的霞和一些孤立点。 这个算法的复杂性为o ( 刀2 ) 。其中一为门槛图的顶点数。 我们定义图g 的中心为c 2 - t ( 0 3 = = 1 f 舛= 矿 。对门槛圈g ，由定义有： 性质1 1 1 ( 1 ) 如果g 是门槛图，则对垤c 明r g ) g 【硼和q y ( g ) 一硼都是门槛图 ( 2 ) g 是 j 槛氅，则每个连通的导出子图研羽( s 矿蜉) ) 满足c e n t ( g s ) 彩 ( 3 ) g 是门槛圈当且仅当g 【y ( g ) 一c e n t ( a ) 是门槛图。 ( 4 ) g 是连通的门槛图。如果矿( g ) 一o e n t ( g ) 0 。则c 4 v ( g ) 一c e n t ( g ) 至少含两 个连通分支。 若g 是连通的门槛图，由上述性质( 2 ) 我们有k = 尉( g ) a ，令q = g ， g i v ( g ) - v j = qu g , u u q ，q 是g 【矿缁 一巧】的连透分支，i e ! r 3 。由上述缝 质( 1 ) 可知q 是门槛图，令v l = c e n t ( g , ) 彩 0 ，其最大团为 c = q 仁i x ! = ： 】- 且i c i = 荟屯 证明：由定理1 1 3 ( 3 ) 知道，图1 3 中c ：g 【p i 石u 虼 】是一个极大团，又 由门槛图中心树的特征知道每一层中o = o l ，) 包含的顶点数最多因此 c = g 【 x l x 望 】是包含顶点数最多的团，所以c 5 q x i x 婪 】是门槛图的最 大团。而包含原图中的毛个顶点所以i c l = 七i i o 定理1 2 2 连通的门槛图g 的最小边割集都是平凡的，其边连通度要么是 i c e n t ( g ) i ，要么是i v ( o ) l - 1 。 证明：如果g 不是完全图。则必有如图1 3 形式的中心树，显然边割集 【，】o = l ，q ) 包含的边数最少。此时，g 的边连通度是l 耐( g ) i a 如果g 是完全图，最小边割集当然是【 磅， 西】，矿( g ) 。此时，g 的边连通度 是l 矿( g ) 卜1 。 1 2 2 门槛图的最大独立子集问题和正常染色问题 设s 是图g 的一个独立子集若不存在其它独立子集能包含s 。则s 称为g 的 极大独立子集。包含顶点数最多的极大独立子集称为g 的最大独立子集。 我们先由门槛图的中心树构造它的树形代表，记为乃( g ) ( 不引起混淆时简记 为乙) ，再通过乃( g ) 的性质找它的最大独立子集和它的色数 算法i 2 1 门槛图乙( g ) 的构造 ( 1 ) 令矿( 乃) = 联g ) ； ( 2 ) 把中心树中包含的顶点按度数非增的顺序连成一条有向路 7 青岛大学硕士学位论文 = v 1 响v 2 - ，0 咭哇； ( 3 ) 加边。乏，y ：) ，o 等，v ：) ，( v 毒，畦) ，心，咭) ，晚，哇) ， d ，唁) ( 吒吃) 对应于图1 3 的乃如图1 4 t 个 圈1 4 对应于圈l3 的乃 门槛图的乃( g ) 是棵带根的树根节点，( 乃) 到顶点，的路所包含的边数叫做顶 点，的高度。比较中心树乏和树形代表乃( g ) ，我们得到： 定理1 2 3g 为连通的门槛图，乃( g ) 为其树形代表，则乃( g ) 的所有叶子节 点构成g 的最大独立子集。 证明： 由乃( g ) 的构造知乃( g ) 中处在同一高度的顶点在原图中互不相邻，而 且不在同一层的叶子节点在原图中也互不相邻，所以所有叶子节点构成g 的一个独 立子集。记为s 。如果再给s 中加入g 的其它任一顶点它就不再是独立子集了， 所以s 为g 的极大独立子集，而且它是g 中包含顶点数最多的极大独立子集，即为 g 的最大独立子集。 8 第一章门槛图中的优化问题 定理l 2 4 连通的门槛图卜( 1 ) ( 其中 o ) 的色数为棚g ) = 毛。 证明：g 是门槛图由定理1 2 1 知，c = q x lx u 圪 】是团。所以 i o 。 蒯 g ) 毛。，再由定理1 2 3 的证明过程知如果先把c = q 戈l x u 吒 】中的点染 扣0 上互不相同的颜色，再把在乃( g ) 中处在同一高度的顶点染成相同的颜色，就可以 ， 得到g 的一个正常染色，所以又有硼g ) 毛因此有r ( g ) = 岛 如0讧o 1 2 3 门槛图的哈密尔顿性 参看图1 3 ，我们给出它的节点的一种标号，称为日标号： f 毛一钆l l i = 0 日( ) = 毛一钆- f = l ，一l l - 0 ，= ， 其余节点标号为0 。 参看图1 3 ，假设有( k ) o ( ，= 1 ，一1 ) ，而我们能通过把吃中的某些点 移到中( s ) 的方法得到一棵修改过的“中心树 ，且该图的胃一标号o ， 那么我们就称这样得到的图为日一树。 定理1 2 5g 是连通的门槛图，其标准表示形式为卜( 1 ) ，中心树如图1 3 所 示。则g 是哈密尔顿图的的充要条件是日标号0 或可以构造日一树。 证明：充分性：情形l 。门槛图中心树的日标号0 在这种情形下，门槛图 一定含有哈密尔顿圈，按图1 5 所示方法寻找其哈密尔顿圈。从第，层由左向右出 发如果最开始的节点中包含的顶点数多于一个，把这些点置于一条路上，之后走 向该节点的父节点中包含的一个顶点，再由该顶点走向下一个子节点中的顶点，把 该子节点的顶点置于一条路上，之后走向该节点的父节点中包含的下一个顶点。如 此下去。这条路会经过所有的顶点，而根节点中的顶点与出发点在原图中有边相连。 这条路再加这条边就得到原图的一个哈密尔顿圈。这就是说小标号0 时该门 口 青_ 黼大学硬士学位论文 槛蜜是啥密尔顿圈 铡1 。2 1 ) 。 翻1 5 寻找蜍密尔顿翻 情形2 ，娥虼) 0 ，存在某些形的辩- 标号小于零( i = l ，) 。这里萄包含有 两种情混。第一种情况，从出发开始检查錾的标号，把中除去瓴+ 玲个顶点剩 余的顶点留借给竹巧，此时查看是否日- 标号0 ，若还存在k 的标号小于零，再检 查巧，若凰暇p0 ，继续这个检查“借点 的过程。如此下去，这一过程能进行到 使俄吃；) o ，也就是说能够构造出嚣一树，那么就转换为第一种惰形了，粼原图 有哈密尔顿圈( 例1 2 2 ) ；第二种情况。若把所有能借的点借完之后，仍有某个 嚣k ) 0 ，( f 警毛，尹一1 _ ) ，即承标号 o 且不能构造置一树，剃图l 。5 所示过程必 然终止于某个只包含一个顶点的节点k 。，丽与v 吒在原图中相邻的顶点都已经在 之前走过的路上了。所以无法从，出发到达下一个顶点了，原图没有哈密尔顿圈， 不是啥密尔顿圈( 例1 2 3 ) 。借点的可行性是由中心树的性质决定的。借点过程如 图1 6 所示： 第一章门槛髓中酌优纯词题 翟1 6 耳一树懿稳造 情形3 。h ( v o ) 【去iv i 】对一个边正常染色，各种颜色所 染的边数最多达到【兰i 矿l 】，所以如果一个图的边数超过【丢i 矿i 】也就是说，一个 图如果是边过剩的，那么它的边染色指数为a + i 。但是判断一个图的染色指数到底 是哪个却并不容易。虽然在完全图和二分图中这是一个p 问题，但在一般图中它已 被断定是a r p c 问题。关于门槛图的染色指数有以下结果： 定理1 2 6 1 4 1 门槛图的染色指数为当且仅当下列情况之一成立： ( 1 ) ( g ) 是奇数； ( 2 ) ( g ) 是偶数且不是边过剩的。 1 2 6 门槛图的拉普拉斯谱和支撑树数目 以g ) = d ( g ) 一钺g ) 称为g 的拉普拉斯矩阵。其中d ( g ) 和4 ( g ) 分别是g 的度 1 5 青岛大学硕士学位论文 对角矩阵和邻接矩阵。l ( o d 是奇异的半正定对称矩阵。令九，丸，是烈g ) 的特征 值，a 为非负整数。烈丘，g ) = d e t ( 甜一以g ) ) ，则q ( 五，g ) = o , ie o , t , ，n - l 。不妨设 o 气 s 五一。由于d d h g ) = 0 所以凡= o 令p ( 凡g ) = 万1 9 ( x ，g ) ，则 p ，g ) 是多项式，令s ( g ) = a ，4 , - 是其根的集合，我们称p ( x ，g ) 为拉普拉斯 多项式，s ( g ) 为g 的谱。令q 寻找各连透分支q ，g 2 ，q 酶最优标号； ( 3 ) 利用卜( 2 ) 计算qu g 2u u g l 的最优标号； ( 4 ) 把r 中的点逐个以通用点形式加入，带宽由1 - ( 3 ) 算出。 这个算法的复杂性为饿羟2 ) ，露为拟门槛图的顶点个数。 2 0 第二章拟门槛闰中的优化问题 2 。2 3 。拟门槛豳鲶晗菘尔顿性 设非空点集s 是g 的顶点集的子集，记g s 的连通分支数为叫g 一t 是以 ，为根的树形蹰，f 是包含，的r 的子树，令烈r ) 表示矿一以r ) 中与，相邻的顶 点个数。8 ( r ) = m i n | v ( t ) | - u ( t ) ：r 是r 的包含根，的予树。 判定一般图的哈密尔顿性是a r p c 问题对拟门槛图，有下述定理： 定理2 。复2 令g 是连通的揆门槛圈( 鞠回麓。t 为冀树形代表。则下摊条侔 等价： ( 1 ) g 是咯整尔顿图； ( 2 ) 烈g s ) - 艺o 赫 出假设知如果联z ) o 则g ( 霉) 有哈密尔顿路；如果文z ) = 0 嚣岱符 。 证明：我们不妨设g 为连通图，f 是棵带根的树。如果尸只有一个顶点，则 = 莎，以( g ) = 亿 = o 。如果f 是顶点不少于两个的星，划f 只有一个顶点此 时以鼢燃q 秽) 燃l 。 假设g 不是星，d 是其最小边控集合。对于f 中的任意条从根，到叶予v 的 青南路p 。至多有它的一令顶点与d 中的边无关联。假设边俐d ，w p 。我们 记p 的顶点集为矿( 尸) 。与d 中边相关联的g 中的顶点集记为矿p ) 。若 第二章掇门槛霉中钓饩化伺题 w 一氓d ) = 嚣 ，p 一删+ 艄还是g 的最小边控集合；蓍幽) = 矿( 研，氨包含一 异于q w 的顶点并。则d v w + a w 是g 的最小边控集合；若 矿酽) = 啊- r ，田匕矿( 研，则d 一、钟十是g 的最小边控集合，y 是，中与，相 邻的嚣叶子节点。无论何种情况，我们都可以把p 孛与d 中边无关联的顶点转为时 子节点v 。因此，y ( d ) 鬻矿伊。) 。也就是说，d 是g 的边覆盖，这就有九( g ) q ( g ) 。 反之，g l 的边覆盖覆盏了g 所有顶点，菰且f 的所有叶子节点构成g 的独立子集， 这就有以( g ) g ( g ) 。所以有六( g = o 够) 。 因为对任意图都有q ( g ) + ( g ) 爿矿( g ) i ，( g ) 表示图g 的最大匹配所含边的 条数，面圈的最大珏甏闯题咒经解决了，所以有了上述定理就可以解决拱门槛图的 边控问题了。 算法2 复3 求拟f j 槛圈g 的边控数疋簸) 设g 为连通的拟门槛图 ( 董 构造g 的树形代表f ； ( 2 ) 去掉f 的所有叶子节点得f ，构造g ； ( 3 ) 求出g 的最大逸配膨，计算掰| ( g ) 司材i ： 膨 5 推论2 2 3 连通的门槛图l 一( 1 ) 的边控数为苁 ) = 去( 颤一重) 或 l l o 笠( g ， i l 眨 冬一1 ) 】+ l r i - o 证明：参看图1 4 ，门槛图g 的树影代表去掉所有叶子节点后是一条路，它的 导出图d 是一个团，且l g j ；f l 。若( j ；f 1 ) 为偶数， g 的最大匹配膨是完 如o如o t， 美匹既，盯正好也是的最小边覆盖，因此兀( g ) = c | ( d ) 嚣寺( 岛一1 ) 若( 毛一1 ) 2 4 第二搴掇门擞豳中韵优化秘题 为奇数td 的最大匹配妊覆盖了g 的 矿lg | 一1 ) 令顶点，匿此 笠姆) = o ( g + ) 黛| 材l + l 篇唼( 镌一1 ) 】+ 薹。 1r 抽0 2 5 结论 结论 本文深入讨论了门槛图和拟门槛图的结构以及这两类图上的一些优化问题。 无论是对门槛图还是拟门槛图的讨论，我们都是从研究结构出发的。这两类图 的特殊结构使得我们能够设计多项式时间算法解决其上的一些优化问题，因为某些 问题在一般图上是肿一c 问题，但在这两类图上是尸问题。 第一章我们借助门槛图的树形代表算出了它的色数，找到了它的最大独立集； 借助门槛图的中心树解决了这类图上的最大团问题、最小边割集问题、带宽问题和 哈密尔顿性问题。 第二章我们构造出拟门槛图的树形代表和中心树以后，用它们反映的拟门槛图 的结构特点解决了拟门槛图上的染色问题、最大独立集问题、团覆盖问题、哈密尔 顿性问题、带宽问题和边控问题。 本文深入的讨论完善了前入的研究成果，但在拟门槛图中还有一些优化问题有 待于进一步研究，比如拟门槛图的染色指数问题和支撑树数目以及这两类图的性质 是否能推广到更一般的图上等等。 2 6 参考文献： 参考文献 1 j 。a b o n d y ，u s r m u r t y ，g r a p ht h e o r yw i t ha p p l i c a t i o n s ，m a c m i l l a nl o n d o na n d e l s e v i e r ，n e wy o r k ，1 9 7 6 。 2 s m a ，w u w a l li s ，j 。w u ，o p t i m i z a t i o np r o b l e m so nq u a s i t h r e s h o l dg r a p h s ，j c o m b i n f o r m s y s t e ms c i 1 4 ( 1 9 8 9 ) ，l 一3 3 s d n i k o l o p o u l o s ，r e c o g n i z i n gc o g r a p h s a n dt h r e s h o l d g r a p h st h r o u g ha e l 曩s s i f i c 8 t i o 珏o ft h e i re d g e s 。i n f o r m 。p r o c e s s l e t t 。? 5 ( 2 0 0 0 ，1 3 5 - 1 3 6 4 c a r m e no r t i zz ，d i f f i c u l tp r o b l e m si nt h r e s h o l dg r a p h s ，e l e c t r o n i cn o t ei nd i s c r e t e m a t h e m a ti c s1 8 ( 2 0 0 4 ) ，2 - 4 5 p l h a m m e r ，a k k e l m a n s ，l a p l a c i a ns p e c t r a la n ds p a n n i n gt r e e so ft h r e s h o l d g r a p h s 。d i s c r e t ea p p l m a t h 6 5 ( 1 9 9 6 ) ，2 5 6 - 2 7 3 1 6 n i k o l o p o u l o s ，s 。d ，p a r a l l e la l g o r i t h m sf o rh a m i l t o n i a np r o b l e m so n q u a s i t h r e s h o l dg r a p h s ，j p a r a ll e ld i s t r i b c o m p u t 。2 0 0 4 ，5 0 5 3 ? 】j 嚷。y a n ，j - j 。c h e n ，g 。j 。c h a y ，q u a si t h r e s h o l dg r a p h s 。d is c r e t ea p p l ，m a t h 6 9 ( 1 9 9 6 ) 。i - 8 8 】l 。s u n i lc h a n d r a n ，m i n i m u mc u t s ，g i r t ha n das p e c t r a lt h r e s h o l d ，i n f o r m a t i o n p r o c e s s i n gl e t t e r s8 9 ( 2 0 0 4 ) ， 1 0 5 11 0 9 康玉霞，许成，千释丽门槛图中的熄优化问题青岛人学学报( 臼然科学版) ，2 0 0 7 ， 2 0 ( 3 ) ，3 0 - 3 2 1 0 康玉霞。许成，张华，于春丽s o m eo p t i m i z a t i o np r o b l e m so nt h r e s h o l dg r a p h s 中国 运筹学会2 0 0 7 年第二篇国际对策论大会会议论文集，9 5 - 9 7 11 v c h v a t a la n dp l h a m m e r ，s e t p a c k i n ga n dt h r e s h o l dg r a p h s ，r e s r e p t c o r r7 3 2 1 u n i v e r s i t yo fw a t e r l o o ( 1 9 7 3 ) 。 1 2 e g c o f f m a nj ra n dg s l u e k e r ，p r o b a b i l i s t i ca n a l y s i so fp a c k i n ga n dp a r t i t i o n i n g a l g o r i t h m s ( w il e y ，n e wy o r k ，1 9 9 1 ) 1 3 j 醚。c h g o l u m b i c ，a l g o r it