（计算机软件与理论专业论文）k支配边临界图的哈密顿性和最小边数.pdfVIP

摘要 图的支配问题是近年来图论中一个比较活跃的研究领域，有很多实际的应用。1 9 8 1 年c o c k a y n e 等人证明计算任意图的支配数是一个n p 困难问题。对于一些特殊图， d e w d n e y 证明了计算二分图的支配数是一个n p 困难问题；b o o t h 等人证明了计算弦图 的支配数是一个n p 困难问题；y a n n a k a k i s 等人证明了计算线图的支配数是一个n p 困 难问题。研究和支配数相关的临界问题，对于解决一般的n p 困难问题，有重要的理论 意义。 图的支配问题中有一个很重要的分支就是图的支配临界问题。图的支配临界问题主 要分为两大类，一类是图的支配边临界问题，另一类是图的支配点临界问题。本文主要 n n ；t n 机计算与数学推理证明相结合的方法，针对支配边临界图，研究其哈密顿性质 和最小边数性质。 w o j c i c k a 猜想所有3 连通，4 支配边临界的图都是哈密顿图，并进步猜想限1 ) 连 通的，k 支配边临界的图都是哈密顿图。本文构造了一类3 连通4 支配边临界的非哈密 顿图，从而证明k = 4 时w o j c i c k a 猜想不成立。 厂( ”，女) 表示具有 个顶点的t 支配边临界图的最小边数。对于k = - i 和k = - 2 ，易知： 厂( 儿i ) = 丁n ( n - 0 ，1 厂( 门，2 ) = _ ( n - 1 ) ( n - 2 ) 。s u f n n e r 猜想( 3 ) s 鱼二掣，本文对奇 数和偶数分别构造了k 支配边临界图，给出了厂( ”，k ) 的个上界： f ( n ，女) ( ( n + 3 k ) ( n - ，k - 1 ) ( 、k 4 ， 4 k 一3 ) 。 关键字：支配图；支配边临界图：哈密顿图；最小边数 a b s t r a c t t h ed o m i n a t i o np r o b l e mi sa na c t i v i t yf i e l do f g r a p ht h e o r yi nr e c e n ty e a r sa n di th a sa l o to fa c t u a la p p l i c a t i o n s i n l 9 8 1 ，c o c k a y n ep r o v e dt h a tt h ec a l c u l a t i o no ft h ed o m i n a t i o n n u m b e ro na r b i t r a r yg r a p hw a san p h a r dp r o b l e m t os o m ep a r t i c u l a rg r a p h s ，d e w d n e y p r o v e dt h ec a l c u l a t i o no fd o m i n a t i o nn u m b e ro nb i p a r t i t eg r a p hw a san p - h a r dp r o b l e m ； b o o t hp r o v e di to nc h o r dg r a p h ；y a n n a k a k i sp r o v e di to nl i n eg r a p h s or e s e a r c h i n gt h e p r o b l e m sc o r r e l a t i v et od o m i n a t i o n h a sg r e a tt h e o r ym e a n i n g t h ed o m i n a t i o n c r i t i c a lp r o b l e mi sa ni m p o r t a n te m b r a n c h m e n to fd o m i n a t i o np r o b l e m i th a st w oc l a s s e s ：o n ei sd o m i n a t i o n e d g e c r i t i c a lp r o b l e m ；t h e o t h e ri sd o m i n a t i o n v e r t e x c r i t i c a lp r o b l e m t h i sp a p e rm a i n l yn s e st h ec o m b i n eo fc o m p u t e r sc o m p u t a t i o na n d m a t h e m a t i cr a t i o c i n a t i o n ，a i m sa th a m i l t o na n dm i n i m u me d g e sp r o p e r t i e so nd o m i n a t i o n e d g e c r i t i c a lg r a p h w o j c i c k as u p p o s e d t h a ta l l 3 - c o n n e c t e d ，d o m i n a t i o n4 - e d g e - c r i t i c a lg r a p h s w e r e h a m i l t o ng r a p h s h ea l s o s u p p o s e d t h a t a l l ( k - i ) 一c o n n e c t e d ，d o m i n a t i o nk - e d g e c r i t i c a l g r a p h sw e r eh a m i l t o ng r a p h t h i sp a p e rg i v e s o u tas e r i e so f3 - c o n n e c t e d ，d o m i n a t i o n 4 - e d g e c r i t i c a lg r a p h sw i t h o u th a m i l t o nc y c l e s ow ep r o v e t h a tw o j c i c k a sc o n j e c t u r ec a n n o tc o m ei n t oe x i s t e n c ew h e nk = 4 f ( n ，k ) d e n o t e s t h em i n i m u m e d g e so f d o m i n a t i o nk - e d g e c r i t i c a lg r a p hw i t hnv e r t e x e s ， e a s i l y w ec a n g e t ，( ”，1 ) ：坐2 ，( ，2 ) ：( n - 1 下) ( n 一- 2 ) ，s u m n e r c o n j e c t u r e d 厂( ”，3 ) 玉堕兰萼旦塑t h i sp 印e rg i v e s 。u tt w o c i a s s e s 。fd o m i n a t i 。n 肛e d g e - c 州c a lg r a p h r e s p e c t i v e l yw t a e nk i se v e l la n d o d d ，p r o v e s t h a t ： f ( n , k ) _ 4 k - 3 ) k e y w o r d s ：d o m i n a t i o ng r a p h ：d o m i n a t i o ne d g e c r i t i c a ig r a p h ：h a m ii r o n i a n ； m i n i f f l u me d g e s ! 塞望望堕量望塑堕童塑堡塑墨! ：望塑 o 前言 图论是应用数学的一个重要分支，它有着广泛的应用背景。随着计算机技术的出现 和进步，图论的理论有了更快的发展，对解决实际问题起到更大的作用。 图的支配问题是近年来图论中一个比较活跃的研究领域。1 9 7 7 年，c o c k a y n e 和 h e d e t n i e m i 关于支配问题的综述文章只有2 0 篇文献。1 9 9 0 年研究支配问题的文献达到 4 0 0 篇。目前，这一领域的文献已超过1 0 0 0 篇，且每年还在稳定增长。 1 9 8 1 年c o c k a y n e 等人“1 证明计算任意图的支配数是一个n p 困难问题。对于一些特 殊图，d e w d n e y 。3 证明了计算二分图的支配数是一个n p 困难问题：b o o t h 等人”1 证明了 计算弦图的支配数是一个n p 困难问题；y a n n a k a k i s 等人“1 证明了计算线图的支配数是 一个h p 困难问题。研究和支配数相关的临界问题，对于解决一般的n p 困难问题，有重 要的理论意义。 图的支配问题是在实际问题中提出的，主要应用于通讯网络中。例如：在一个通讯 网络的一些节点上放置发射器，要求每个没有发射器的节点一定和某个有发射器的节点 有一个直接的通讯线路。如何选择节点，使得放置的发射器数目最小。 图的支配临界问题是图的支配问题的一个重要分支。图的支配临界问题主要分为两 大类，一类是图的支配边临界问题，另一类是图的支配点临界问题。学术界对支配临界 图的性质，目前的研究主要集中在以下几个方面： 1 1 完备匹配 3 ) 分支与块结构 5 1 独立支配数 7 、最小边数 2 1 哈密顿性质 4 1 直径 6 ) 顶点的度 本文主要是针对支配边临界图，研究其哈密顿性质和最小边数。 w o j c i c k a 5 1 证明了如果g 是连通的，3 支配边临界，顶点数大于6 的图，则g 有一 个哈密顿回路。w o j c i c k a l 5 进一步猜想每一个连通的，3 支配边临界无割点的图都有一 个哈密顿回路。这一猜想被f a v a r o n q 和t i a n 7 】证明是成立的。c h e n 等人【8 1 给出了这个 猜想的一个新证明。 w o j c i c k a t s l 还猜想所有3 连通，4 支配边临界的图都是哈密顿图，并进一步猜想( k - 1 ) 连通的，k 支配边临界的图都是哈密顿图。本文构造了一系列3 连通4 支配边临界的非 哈密顿图，从而证明了k = 4 时w o j c i c k a 猜想是不成立的。同时给出了一系列无割点的， 无哈密顿回路的k 支配边i 腹界图，为解决k 4 时w o j c i c k a 猜想提供了思路。 f ( n , k ) 表示具有h 个顶点的i 支配边临界图的最小边数。易知厂( 珂，1 ) = n ( 丁n - 1 ) k 支配边临界图的哈密顿性和最小边数 m ，2 ) = ( n - 丁1 ) ( n - 2 )，s u m n e r 9 1 猜想厂( ”) 3 ) 鱼掣，本文对i 为偶数或奇数分 别构造了k 支配边临界图， 给出了f ( n ，女) 的一个上界 f ( n , k ) _ 4 , n 4 k - 3 ) 2 ! 塞墼望堕墨璺塑堕童塑堂塑墨尘望垫 1 支配图基础知识 1 1 支配图起源及应用 图是实际问题的抽象表示。图的本质内容是顶点和边之间的关联关系，至于顶点和 边是否用平面上的几何点和线段来表示、顶点和边的实际意义等，则是无关紧要的。 支配图问题起源于棋类的游戏问题。1 8 5 0 年，欧洲的象棋爱好者考虑了这样一个问 题：在一个标准的8x8 的国际象棋棋盘上放置一个皇后，在棋盘上怎样放置若干个皇 后，可以让棋盘上所有的位置或者在皇后攻击的范围内或者被皇后所占领。 支配图在实际应用中有很广泛的应用。例如在一个电网系统中，在某些节点上放置 一些监视器，监控网络的运行情况，则如何放置监视器，使得监视器的数目最小，且可 以监控所有节点。见图1 1 。图中的顶点表示可以放置监视器的节点，两点之间的连线 表示监视器可以监控与其直接相连的节点。则监控网络的问题可以抽象为一个支配图的 问题。 图1 1 电力网络图 f i g u r e l 1e l e c t r i cn e t w o r kg r a p h 在计算机通讯网络中，支配问题也有重要的应用。我们考虑一个计算网络，假设其 模型为g ( v ，e ) 。g 中的顶点表示处理器，边表示一对处理器之间的直接通讯连接。每 一个处理器能够给与它直接相连的处理器传送信息。假设我们需要不断的从所有处理器 取得信息。我们让每个处理器将自己的信息传给一个搜集信息的处理器的集合。因为这 个过程需要相对的快速的处理，所以我们不能让信息在过长的路径上传输。因此我们需 要指定一个对所有处理器都相对近的处理器集合。假设我们对信息的传输最多能忍受2 条路径的路径时延，怎样才能找到满足条件的处理器集合，使得处理器的数目最少。该 问题称为距离2 支配问题。如图1 2 。 k 支配边临界图的哈密顿性和最小边数 图i 2 距离2 支配图( s = f v ，v ：) ) f i g u r e l 2d i s t a n c e 一2d o m i n a t i o ng r a p h ( s = “，v 2 ) 1 。2 支配边临界图简介 睾配临界罗垄支配图的一种。一个图g 是k 支配边临界的( 简称i 边临界) ，当且 堡堂坠2 ) 2 七并且对任意不邻接的两个顶点“，v e g ，有，( g + 。) = k - 1 。y ( g ) 衾示鬲舌 的支配数。 。 一。一“ 对于1 支配边临界图和2 支配边临界图，很容易得到： 定理1 1 ：一个图g 是1 支配边临界图当且仅当g 是完全图。 定理1 2 【9 】：一个图g 是2 支配边l 临界图当且仅当g 是星图的并的补图。 即虿= 譬t 丘幽1 ) 。 ：定理1 2 耸堂，箜2 支配边临界图是b a u e r 1 川等人定义的支配临界图的补图，w a l i k a r 和a c h a r y a l l l l 也研究了这一类图。 七支配边临界图的哈密顿性和摄小边数 图1 4 一个简单的3 支配边临界图g ， f i g u r e l 4a s l m p l e3 - e d g e c r i t i c a ld o m i n a t i o ng r a p hg 3 图g ，是一个3 支配边临界图，可以由如下分析得到： 取s 2 4 ，5 ，6 ) ，| s i 2 3 ，又因为不能找到更小的支配集，所以，( g ，) = 3 。对于图 g ，中的任意两个不相连的点，增加一条边，有两种情况： 1 ) 连点1 和点2 k 支配边临界图的哈密顿性和晟小边数 2 ) 连点1 和点5 若为1 ) ，可得到g ： 图1 7 g 3 一f ( s = l ，2 ，3 ) f i g u r e l 7 g 3i ( s = 1 , 2 ，3 ) ，g ，为3 图的例子： 4 若为2 ) ，可得到。 图1 8 g 3 一：( s = l ，2 ，3 1 ) f i g u r e l 8g 32 ( s = 1 ，2 ，3 ) 3 ! 塞墼垄堕墨里堕堕童塑堡塑墨尘竺塑一 1 3 支配边临界图性质 如果v 和“是七支配边临界图g 的不相邻顶点，那么一定存在一个元素个数为七一2 的集合s 满足： 1 )s u v ) 支配所有的g 一“； 2 )s u f “) 支配所有的g v 。 第一种情况，记做 v ，s 】哼“，第二种情况，记做州斗v 。特别的，我们记 v ，s 】辛“， 表示“不被s u f v 支配。 因此，v 斗“表示存在一个j i 一1 个元素且包括v 的集合s u v ) 支配所有的g 一“中的 元素。显然，如果图g 是支配边临界图，那么对于任意的一对不相邻的顶点v 和狂，或 者v 斗“或者“斗v 。 通常，对于一个图删去一个顶点会导致支配数的急剧增加。例如，对蜀。，它的支 配数是1 ，如果我们删去中心点，则所得结果图的支配数为订一1 。对于边临界图，删去 一个顶点不能增加支配数。： 定理1 3 【9 】：如果v 是一个支配边临界图g 的任意一个顶点，那么r ( c v ) 女。 一个七支配边临界图g 的子图g 为这个詹支配边临界图的核，如果对任意的一个顶 点v v ( g ) ，有y ( g v ) = 女一l 。 定理1 4 【2 ：对于任意连通的，七支配边临界图g ，如果g + 是非空的，那么g 是一个 完全图。 f a v a r o n ，s u m n e r 和w o j c i c k a t l 铂提出了一种简单的方法来把一个七支配边临界图扩 展为一个更大的尼支配边临界图。设存在图g ，有v 矿( g ) ，v 。茌矿( g ) 。则 表 示具有点集v ( g ，v ，v ) = y ( g ) u ) 和边集e ( g ，v ，v + ) = e ( g ) u v ”：“p 】) 。因此， 是通过从图g 加上一个和点v 有相同临闭集的点v 得到的。如果g 是膏边临 界的， 也是斤边临界的，则v 被称为可扩展的。 定理1 5 【1 3 】：如果点v 是图g 的一个顶点，v 是可扩展的当且仅当对于每一个“茌n v 】， 有v “。 1 4 本文工作 本文主要是研究支配边临界图的哈密顿性质和最小边数性质。 我们通过计算机编程计算，找到了一个3 连通，4 支配边临界的非哈密顿图。由这 k 支配边临界图的哈密顿性和最小边数 个基本图，我们构造出了一系列3 连通，4 支配边临界无哈密顿回路的图，从而证明了 k = 4 时w o j c i c k a 猜想不成立。同时，我们还构造了一系列无割点的，无哈密顿回路， k 支配边临界的图，为解决k 4 时w o j c i c k a 猜想提供了思路。另外，本文还研究了支 配边临界图最小边数的性质，给出了满足一定条件的n 个顶点，k 支配边i 晦界图的最小 边数的一个上界： 肼， _ _ 4 , n 4 k - 3 卜 1 5 相关概念 为了在本文的讨论中避免歧义，先说明一下本文使用的相关术语和概念【1 8 1 1 2 1 】i 冽【2 3 1 。 夺图 一个无向图g 定义为个二元组( 矿，e ) ，记作g = ( 矿，e ) ，其中v = y ( g ) 是一个非 空集合，称作无向图g 的顶点集：e = e ( g ) 是由v ( g ) 中元素构成的无序对集合，即 e ( g ) = ( “，v ) i “，v 矿( g ) ) ，称为无向图g 的边集。简记边( 甜，v ) 为u v 。 一个有向图g 定义为一个二元组( 矿，e ) ，记作g = ( 矿，e ) ，其中矿= 矿( g ) 是个非 空集合，称作有向图g 的顶点集：e = e ( g ) 是由矿( g ) 中元素构成的有序对集合，即 e ( g ) = “，v 矿( g ) ) ，称为有向图g 的边集。 无向图与有向图统称为图。无特殊说明的图一般是指无向图。 边驯的端点“，v 称为相邻的。称一条边的端点为与这条边相关联，同时，也称一 条边为与它的端点相关联。若两条不同的边与一个公共的顶点关联，则称它们是邻接的 边。 p = p ( 回= 联g ) | 表示图g 中的顶点数，称为g 的l b q ( o r d e r ) 。 q = g ( g ) = 陋( 】表示图g 中的边数，称为图g 的大小( s i z e ) 。 夺支配集 s 是一个图g 的顶点集的子集，如果对不属于s 的图g 的任意顶点，至少和s 中 的一个顶点相邻接，称s 是图g 的支配集。 夺支配数7 ( g 1 元素个数最少的支配集称为最小支配集。最小支配集的顶点个数称为这个图的支配 数，记作r ( g ) 。 夺肛支配边临界图 一个图g 是虹支配边临界的( 简称船边临界) ，如果y ( g ) 哥并且对任意不邻接的 6 正支配边临界图的哈密顿性和最小边数 两个顶点7 , l 和v 有r ( g + u v ) = k - 1 。 冷缸支配点临界图 一个图g 是舡支配点临界的( 简称“点临界) ，如果y ( g ) 或并且任意去掉一个顶 点“，有z ( g 一“) = k - 1 。 夺完全图 完全图k 。是顶点数为p 且每一对顶点都邻接的图。 夺二部图 如果一个图的顶点集能被分成两个不相交的集合k ，砍( 称为部分集) ，且每条边将 巧中的顶点与中的顶点相连，则称此图为二部图，有时也称为二分图或偶图。若k 中 的每乏点号中的每个顶点都相邻，则称此二部图为完全二部图，记为k 。，。，其中 p t = k | ，p ：= 1 i 。 夺星图 p + 1 个点的星图有p 条边，且这p 条边的一端都连着同一个顶点，另一端连其他p 个点。记为k 。 夺补图 1 一个g 的补图万也是以矿( g ) 为顶点集的一个图，两个顶点在虿中邻接当且仅当这 两个顶点在g 中不邻接。 夺图的运算 能用较小和较简单的图来表达一个给定的图的结构是很方便的。对经常出现的图也 值得给一个简单的记法。 g 一碱，e z ，p 。) 表示图g 删除边q ，e ：，后所得到的图。若k = l ，简记为g p 。 g + p - ，e 2 ，8 ) 表示图g 添加边q ，e 2 ，e i 后所得到的图。若k = l ，简记为g + p 。 g 一 v - ，v ：，v 表示图g 删除顶点v 。，v ：，v 。及与其相关联的边后所得到的图。 若七= 1 ，简记为g v 。 g u v ( v 菇矿( g ) ) 表示图g 并上一个孤立顶点v 后所得到的图。 夺路 若途径矽的顶点v 1 ) v ：，v 。互不相同，则称矽为路。 夺v ，“连通 若g 存在( v ，“) 路。连通是顶点集v 上的一个等价关系。于是就存在v 上的一个分 k 支配边临界图的哈密顿性和最小边数 类，把v 分成非空子集k ，圪。两个顶点“和v 是连通的当且仅当他们属于同一子 集f 。 夺连通图 若g 只有一个分支，则称g 是连通的，否则称g 是不连通的。， 令k 连通图 对于图g 中任意肛1 个顶点v 1 ，v ：，v 。v ，删去这知1 个顶点，图g 仍然连通， 则称该图为k 连通图。 夺哈密顿路 顶点数为n 的图中的一个长为m 一1 的恰好包含这个图所有顶点的路称为哈密顿路。 顶点数为 的图中的一个长为n 的恰好包含这个图所有顶点的回路称为哈密顿回 路。 有哈密顿回路的图称为哈密顿图。 令同构 设g = ( k ，e 。) ，日= ( k ，e 2 ) ，若存在k 到k 的一一映射妒，使得对于每一对 “，v k ，“v e l ，当且仅当口o ( u ) c o ( v ) e 2 ，则称g ，同构，简记为g 兰h 同构的图具 有相同的拓扑性质。 一个图g 的一个自同构是图g 与它自身的一个同构。 令相似 若对图g 的某一个自同构a ，口( “) = v ，则称图g 的两个顶点“和v 为相似的。不 相似于其它任何顶点的顶点称为不动点。若有图g 的一个自同构口，使 d ( ( “1 ，v 1 ) ) = ( ”2 ，v 2 ) ，则称两条边p l = u l v l 和e 2 = 2 v 2 为相似的。 夺邻集 对一个点x v ，x 的邻集定义为( x ) = 抄v ( g ) l x y e ( g ) ) 。 夺闭邻集 一梦一个点x en 工的闭邻集定义为n i x = n ( x ) w x ) 。对于一个点集s 矿( g ) ， n s j _ u 。b j 。则如果一个集合s 是支配集，则 司= 矿。 夺完备匹配 个图的匹配是它的一些彼此孤立的边组成的集合，若匹配恰好包括所有的点，则 k 支配边临界图的哈密顿性和最小边数 2 支配边临界图的哈密顿性质 本章研究k 支配边临界图的一个重要问题一哈密顿回路问题。在运筹学、计算机科 学和编码理论中很多问题都可以转化为哈密顿问题，所以研究其哈密顿性质具有重要的 意义。 2 1 哈密顿图简介 包含g 的每个顶点的路称为g 的哈密顿路，g 的哈密顿回路指包含g 的每一个顶 点的回路。这个路和回路的定义是由h a m i l t o n 的名字命名的，因为他在给他的朋友 g r a v e s 的一封信中描述了关于十二面体的一个数学游戏：一个人在十二面体的任意五个 相继的顶点上插上五个大头针，形成一条路，要求另一个人扩展这条路形成一个圈。十 二面体是哈密顿图( 如图2 1 ) ，图中粗线表示一条哈密顿回路。h e r s c h e l 是非哈密顿图f 如 图2 2 1 h 8 。 图2 i 有哈密顿回路的十二面体 f i g u r e 2 1h a m i l t o n i a nt w e l v ef a c eo b j e c t 9 k 支配边临界图的哈密顿性和最小边数 2 2 w o j c i c k a 猜想 图2 2 无哈密顿回路的h e r s c h e l 图 f i g u r e 2 2n o h a r n i l t o n i a nh e r s c h e lg r a p h 是否每一个无割点的3 支配边临界图都存在一个哈密顿回路，是一个令人感兴趣的 问题。w o j c i c k a s l 证明了每一个连通的，顶点数大于6 的3 支配边临界图都有一个哈密 顿路。并猜想每一个无割点的连通的3 支配边临界图都有一个哈密顿回路。 f a v a r o n 等【6 】证明了当口s 占+ 1 时，w o j c i c k a 的上述猜想成立，t i a n 等7 l 证明了 口= 占+ 2 时，上述猜想成立。陈等1 8 1 给出了该猜想的一个新的证明。 其他一些研究人员研究了哈密顿性和3 支配边临界图的连通度之间的关系。s u m n e r 和w o j c i c k a 1 朝提出了一个类似的问题。h a n s o n 1 4 1 通过定义一个闭集操作研究了3 支配 边临界图的哈密顿性质。a o 和m a c g i l l i v r a y 1 5 1 定义了一个类似的闭集操作研究了 h a n s o n 的那一类图。 w o j c jc k a 猜想【5 】：对于任何( 肛1 ) 连通的，k 支配边临界的图都是哈密顿图。 2 3 w o j c ic k a 猜想( k = 4 时) 反例的构造 我们通过编写图的支配边临界判定算法，支配数的计算算法，以及图的哈密顿性的 判定算法，运用计算机计算，找到了一个3 连通( 2 连通) ，4 支配边临界的无哈密顿回 路的图，并由此图构造了一类3 连通，无哈密顿回路的4 支配边临界图，从而证明了k ：4 时w o j c i c k a 猜想不成立。 本节中g 。表示i 连通的，k 支配边临界图。 k 支配边临界图的哈密顿性和最小边数 2 3 1 2 连通、3 连通无哈密顿回路的4 支配边临界图 8 9 图2 3 g ：4 ( s = 0 , 8 ，9 ，1 0 ) f i g u r e 2 3g 24 ( s = 1 89 1 0 ) 图2 4 g ( s = 0 , 2 ，3 ，4 ) f i g u r e 2 4 g 3 4 ( s = l ，2 ，3 ，4 ) ) 2 3 2 7 个顶点3 连通，无哈密顿回路4 支配边临界图( 腔1 3 ) 由图2 4 ，对顶点1 可进行扩展，可以得到一类的w o j c i c k a 猜想的反例。同时，我 们将证明这一系列图是3 连通，无哈密顿回路的4 支配边临界图。 p i 1 p 3 2 ! 塞墅望些墨里塑堕查塑丝翌墨尘望塾一 图2 ，5 力( 虚1 3 ) 个顶点，3 连通，无哈密顿回路4 支配边临界图q f i g u r e 2 5 门( 腔1 3 ) v e r t e x e s ，3 - c o n n e c t e d ，n o h a m i l t o n i a n ，4 - e d g e c r i t i c a lg r a p h 图g 。的构造： g ，= v ( g ，) = w ，“，”，p ，i1 1 i s t ；j = 1 , 2 ，3 ；k 2 l ，2 ， e ( g f ) = m l w j 2 ，w 吩，“p j ，甜毁+ 1 ) 。0 d 3 + l ，p ，段，+ 1 ) m o d 3 + 1 ，i 1 4 。 因此，y ( g ) = 4 。 引理2 2 ：v e e ( q ) ，( q + e ) = 3 a 证明：要证明该引理成立，我们只需对任意g ，+ p ( eg e ( g ，) ) 找到一个支配集s 满足 1 s 1 2 3 。 考虑所有情况，可将p 分为以下几种分别讨论： 1 ) p = w p6 ( 1 sj t ；a = 1 ，2 ，3 ；6 = 1 , 2 ) ，取 s = w ，p o ，v ( “) n o d3 + 1 ) a 2 ) e = w j v 口( 1s t ；a = 1 , 2 ，3 ) ，取 ，。 s = w j ，v 。m o d3 + i ，v ( 川) 。d 川) 。 3 ) 8 = r a t 。3 十l ( a = 1 , 2 3 ) ，取 ! 塞望望堕墨里箜堕童塑丝塑塑型蔓望坠一 s = “。，v 。，【l o d3 “，p ( 。+ 1 ) m o d3 + 1 1 。 4 ) e = u o p 。3 + 16 = 1 , 2 ，3 ；6 = 1 ，2 ) ，取 s = “。，v a , p 。m 。d3 + 1 卜6 。 5 ) e = a v 。 = 1 , 2 ，3 ) ，取 s = u o , 。“3 “l p 。o d * l 。2 ) 。 6 ) e = u a v 。“( a = 1 , 2 ，3 ) ，取 s = ( “d ，“口m o d3 “，p ( 。“) m o d3 + 1 ，1 a 7 ) 8 = g a ”) 。o d3 + l 1 = 1 , 2 ，3 ) ，取 s = 1 。，“( “) m “，p 。，1 ) 。 8 ) e = p “p 陋= 1 , 2 ，3 ) ，取 s = w i ，p n l ，v ( 。+ 1 ) m o d3 + 1 ) 。 9 ) p = p a , b l p 。0 d 6 2 = 1 , 2 3 ；b 1 = 1 , 2 ；b 2 = 1 , 2 ) 1 ，取 s = 。，p 1 ，p 。m o d3 + 1 , 3 - b 2 。 l o ) e = p o , b ”) 。o d3 + 1 0 = 1 , 2 ，3 ；b = l ，2 ) ，取 s = w 1 ，”( 。“) m o d3 + 1 ，p 。 a 儿) e = v 。v 。“3 + l ( a = 1 , 2 ，3 ) ，取 s = ( w l ，v 。，v f 。+ 1 1 m o d3 + i ) 。 从1 ) 到1 1 ) ，我们有对于所有的e 匹e ( g 。) ，( g f + p ) = 3 。 从引理2 1 - 2 2 ，我们可以得到： 引理2 3 ： 是4 支配边临界图。 对于由g ，任意删除2 个顶点得到的图，都为连通图，所以我们有 引理2 4 ：g ，是3 连通的。 引理2 ，5 ：g ，没有哈密顿回路。 证明：我们通过反证法证明。 假设g ，有一个哈密顿回路q ，因为 n g ( p a = 1 , 2 ，3 ；b = 1 ，2 ) ) = “。，v 。id = 1 , 2 ，3 1 ， 1 4 t 支配边临界图的哈密顿性和最小边数 所以我们有： n c ( p 舶1a = 1 , 2 ，3 ；b = 1 ，2 ) ) 量扣。，v 。la = 1 , 2 ，3 。 因为对于所有的v v ( g ，) ，7 苜d c ( v ) = 2 ，则点集 p i 口= 1 , 2 ，3 ；6 = l ，2 ) 必然与点集 扣。，j 口= 1 , 2 ，3 通过1 2 条边相连。对于每一个a a 盯= 1 , 2 ，3 都必须与 儿6l = 1 , 2 ，3 ；6 = 1 ，2 ) 中的2 个点相连，所以不能与 w ，1 1 ，r 中任何点相连。所以， w ，矿( 巴) ，这与q 是g ，的一条哈密顿回路相矛盾。从引理2 1 一引理2 5 ，定理2 1 得 证。 2 5 相关算法 2 5 1 计算图的最小支配数的算法 为了判断图是否为支配边临界图，需要首先计算图的最小支配数。下面给出计算图 的最小支配数的算法m i n d o m i n n u m 1 9 】 2 。1 。 算法：m i n d o m i n n u m 输入：顶点数竹，图g 的邻接矩阵耳 输出：图g 的最小支配数 为了方便表达，取以下记号 心表示编号为k 的顶点。 n e x t ( v 。) = v 。表示取顶点标号比当前点大一的点。 n u 表示点u 的邻集。 p u s h ( s ，v )表示将顶点v 以压栈方式放入s 中。 v 。p o p ( s )表示将s 中栈顶顶点出栈，并将出栈顶点记为v 。 v 2 t o p ( s )表示找到s 中的栈顶顶点，记为v ，但不出栈。 旧表示s 中的顶点个数。 i s d o m i n a t i o n ( s ) 判断s 是否能够支配g 的所有顶点，即s 是否为g 的支配集。 f 咋表示顶点k 的标号k 。 i n tf u n c t i o n m i n d o m i n n u m ( n , 曲 k 支配边临界图的哈密顿性和虽小边数 b e g i n s = 西： p u s h ( s ，v 1 ) ； m i n d o m n u m = n ； l o ：i fi s d o m i n a t i o n ( s ) i f ( m i n d o m n u m l s 1 ) m i n d o m n u m = l s i ； e n d i f i fm i n d o m n u m = = 1r e t u r n m i n d o m n u m ： g o t o l 3 e n d i f i f ( i s l 2 3 m i n d o m n u m ) g o t ol 3 v 2 t o p ( s ) ； 厶：= n e x t ( v ) ； i f l u p ”g o t o l ，； i f ! f l u 芒s ) & & ( j t 0 ) ) & & ( 七g s ) ) g o t o 厶； p u s h ( s ，“) ； g o t o l o l 3 ： i fi s l 1 v 。p o p ( s ) ； g o t o 厶； e n d i f r e t u r n m i n d o m i n n u m ； e n d 算法的主要过程是首先将顶点压入栈s 中，然后判断栈s 是否已经为g 的支配集， k 支配边i 豳界图的哈密顿性和最小边数 并比较i s l 与现有支配数的大小的过程。 1 ) 若s 已为支配集，则判断i s f 的大小与已有的支配数的大小关系，若小于原有支 配数，则将支配数改为l si 。否则判断栈s 中的元素个数是否小于支配数的大小。 若不小于，刚退出栈s 的栈顶元素，否则取出s 中栈顶元素( 但不退出该顶点) ， 计算下一个入栈的顶点。 2 ) 将下一个入栈的顶点压入s ，重复上面过程1 ) 。最后得到的支配数即为s 的最 小支配数。 算法的一个主要工作是找出下一个可能入栈的顶点。每次计算可能进栈的顶点，都 是按顶点编号从小到大的顺序。我们判断若魄萑s ( 顶点编号为毒的顶点) ，且化) 芷s ， 则叱为下一个入栈的顶点，否则判断v 。是否为下一个入栈的顶点。 另外，初始时，设图g 的支配数d o m i n n u m 为g 的顶点数n ，若s 为g 的支配集， 如果i s l 小于d o m i n n u m 的大小，则d o m i n n u m = l s l ，否则继续循环。遍历完所有情况， d o m i n n u m 即为图g 的最小支配数。 2 5 2 判断图是否为支配边临界图的算法 本文需要判断一个给定的图是否为_ j 支配边临界图，因此需要给出一个算法，判断 该图是否为边临界的【1 9 1 20 1 。 算法：i s e d g e c r i t i c a l 输入：g 的支配数k ，g 的临界矩阵 输出：t r u e ：g 是边临界图，f a l s e ：g 不是边临界图 b o o lf u n c t i o n i s e d g e c r i t i c a l ( k ，g ) b e g i n f o re a c he ，gd o f o re a c h e ，g d o i f ( e ，e j ) & & ( ! g 1 们) g i l l = l ； i f ! ( m i n d o m i n n u m ( n ，g ) = ；k - 1 ) r e t u r nr l s e e n d i f ! 塞墼望些墨里塑堕查堡壁塑量尘望整 舡f 阴= 0 e n d i f e n d f o r e n d f o r r e t u r n t r u e ； e n d 算法的主要过程是通过一个2 重循环，遍历g 中所有未连边的一对点，若对所有未 连边的一对点，加上该边后，g 的支配数都减少1 ，则返回t r u e ，表示g 为支配边临界 图，否则返回f a l s e ，表示g 不是支配边临界图。 2 5 3 判断图是否有哈密顿回路的算法 由于判断一个图g 是否有哈密顿回路的充分必要条件尚未找到，本文利用简单的遍 历算法，遍历所有可能，看能否找到一条哈密顿回科1 9 】【2 0 】。 算法：h a s h a m i l t o n 输入：g 的临界矩阵 输出：t r u e 表示存在一个哈密顿回路；f a l s e 表示不存在一个哈密顿回路 为了方便表达，取以下记号 v 。表示编号为k 的顶点。 n e x t ( v 。) = - g 表示取顶点标号比当前点大1 的点。 p u s h ( s ，v )表示将顶点v 压入栈s 中。 v = p o p ( s )表示将栈s 中栈顶元素出栈。 v = t o p ( s ) 表示取栈顶元素。 v = b o t t o m ( s ) 表示取栈底元素。 蚓表示s 中的顶点个数。 1 v 。1表示顶点v 。的标号k 。 b o o lf u n c t i o nh a s h a m i l t o n b e g i n s - = ； l r k 支配边临界图的哈密顿性和展小边数 的所有顶点都进栈，则判断最后一个进栈的顶点是否和第个进栈的顶点相邻，若是， 则该图存在哈密顿回路，否则，将栈顶的顶点出栈，取该顶点编号的下一个顶点，若该 顶点不在栈中，且和栈顶的顶点相连，则将该顶点压入栈，继续循环，直到找到一条哈 密顿回路，返回t r u e 或遍历所有情况，没有哈密顿回路，返回f a l s e 。 2 6 无割点，无哈密顿回路的斤( 脸4 ) 支配边i i 盆界图 在本文研究过程中，还构造出了一系列无割点，无哈密顿回路的k 支配边临界图， 对于研究k 4 时，w o j c i c k a 猜想是否成立提供了思路。 ! 塞望望坚墨塑塑堕童塑壁塑墨尘望塑一 2 6 1 无割点，无哈密顿回路五支配边临界图的构造( 七为偶数) 1 1k 为偶数，k 4 且k 6 图g 具有点集坎g ) 和边集e ( 回，分别为下： 矿( g ) = u u u 尸u 矿) ， w = w 矗， u = 扣l ，“2 ，一1 ， p = p 1 t ，p 1 2 ，p 2 1 p 2 2 ，k 1 1 ，p 2 v = v l ，v 2 ，v ) ， e ( g ) = e ( w u ) ue ( u p ) ue ( y p ) ， e ( w u ) = w l u ，：“，u ，1 i k 一1 ) ， e ( u p ) = “，p “：j u ，p “p ，1 i 七一1 ，j = 1 ，2 ) u “f p ，+ u ：，u ，p u p ，1 i 七一2 ，j = 1 ，2 ) u ( “p l f ：j = 1 ，2 ) ， e ( v p ) = ( v ，p “：v i v ，p u p ，1 i k 一1 ，j = 1 , 2 w v t p f + 1 j ：v v ，p u p ，1 i sk 一2 ，j = 1 , 2 ) u v k - l p l j ：j = 1 ，2 ， k 支配边临界图的啥密顿性和最小边数 图2 6 k 边临界，无割点非哈密顿图( 后为偶数，k s6 ) f i g u r e 2 6k - e d g e c r i t i c a l ，1 3