下载文档原格式
离散数学及其应用教育部重点实验室工作总结报告（2011年3月18日）实验室名称：离散数学及其应用教育部重点实验室主管部门：福建省教育厅依托单位：福州大学实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。
以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。
目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。
实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。
实验室位于福州大学铜盘校区。
2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到“环境优美、设备一流”。
按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。
为每位研究生提供一个工作位及台式电脑。
已建成无线网覆盖实验室3000平米的科研、办公场所。
重视网络建设，保证网络高速畅通。
订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。
一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。
二、在本年度，实验室主任范更华教授获全国优秀科技工作者。
实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重点项目1项，面上项目6项，新增国家973计划课题1项，为1.大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003），范更华新增国家自然科学基金3项，其中面上项目2项，青年项目1项，分别是：1.超大规模集成电路多目标划分的算法研究（），朱文兴，国家基金面上项目。
2.近景摄影测量中的自动图像分割技术（），王美清，国家基金面上项目。
3.几类图染色问题的研究（11001055），侯建锋，国家基金青年项目。
实验室在2010年8月顺利完成了国家重点基础研究发展计划（973计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904）”。
开题报告信息与计算科学哈密顿图的判定与应用一、综述本课题国内外研究动态, 说明选题的依据和意义图论(graphic theory)是一门既古老又年轻的学科. 它诞生于18世纪上半叶. 到19世纪下半叶这个领域才发展成为数学的一个系统的分支, 直到20世纪上半叶, 这门学科才有自己的著作出现. 自20世纪下半叶开始, 随着计算机科学与技术的发展, 图的理论研究和应用研究才得到迅速广泛的重视, 图论作为一个数学的分支, 才真正确立了自己的地位. 哈密顿(爱尔兰科学家)在1859年提出一个名叫“周游世界”游戏问题是: 能否遍历正12面体的每个顶点一次且一次后回到原地. 由此引申出哈密顿图的定义: 如果图上有一条G 经过图所用顶点一次且仅一次的回路, 则称此回路为哈密顿回路, 具有哈密顿回路的图G 称为哈密顿图.哈密顿图具有六个领域: 哈密顿圈, H 连通, 泛圈, 点泛圈, 边泛圈, 泛连通. 哈密顿图是有哈密顿圈的图. 至今没有一个像欧拉图的充要条件那样的“非平凡的”(不是定义的同义反复)关于哈密顿图、哈密顿通路的充分必要条件, 但关于他们的充分性和必要性分别有一些研究成果. 而哈密顿图不光在金字塔图、扇面蜂巢图及马图上有体现它性质的研究, 且在四正则连环图和彼得森中有它独特的应用.而且哈密顿图在哈密顿通路、哈密顿轨、多哈密顿轨问题上也有很多细致的研究和应用.1984年时在连续10年排名加拿大第一大学的范更华教授得到名垂青史的“范定理”: 2连通阶图的距离是2的任意两点均有, 则是有圈, n G ,x y max{(),()}/2d x d y c ≥G c 当时是哈密顿图. 当然, 关于如此著名的范定理, 各国不少专家也对范定理企求做出c n =改进发展. 1987年Wojda 院士和欧洲最古老的著名大学之一的法国奥大的运筹学科创建奠基人Benhocine 教授2人合作仅局部推广上面范定理. 又如法国 Benhocine 教授1977年发表在法国科学院学报的哈密顿图论文就一直有国际影响, 但他至今仅有25篇数学论文且18篇是哈密顿图的, 他是排名哈密顿图研究前30名大师之一.哈密顿图已经历了一个多世纪的跋涉, 容易攀登的时代已经过去了, 其进展已非常不容易, 如此即使是世界级的大师泰斗, 不论你多么聪明利害都好, 面对的下一个问题猜想都永远是相关学科的全世界的专家经过多年仍不能解决的, 就是想做点进展都非常不容易, 每一篇论文都是超越最权威大师的成果. 哈密顿图的难如两个权威说“非常不容易”. 但它却具有重大历史意义以及广泛而重要的应用价值.现国际数学联盟主席是哈密顿图权威, 并且琼州大学赵克文和美国权威等合作改进耶鲁大学Ore 院士等大师权威的代表性结果已在“哈密顿图”居世界领先.在国内, 宁宣熙和宁安琪提出了哈密顿圈自组织算法的实证研究结果和其在哈密顿图判定上的应用, 介绍了SOA 算法在大约 12000个规模不同()104000,208000n m =-=-的一般任意图中构造哈密顿圈的实证研究结果, 验证了SOA 算法的可靠性和时间的多项式性. 在此基础上论证了SOA 算法用于判断一般任意图是否为哈密顿图的可行性, 并用一些实例进行了实证研究. 在阻塞流理论的研究中, 利用网络最小阻塞流与哈密顿轨之间的关系建立了哈密顿轨问题的无环最小支撑流模型. 通过这个模型可以把一步内构造无环最小支撑流这一数学难题分解成分别在多项式时间内完成的两个阶段,从而为解决这一数学难题找到了新的思路,开发研制了在一般任意图中构造哈密顿圈的自组织算法(或SOA 算法). 在文献, 全面详细地介绍了作者经过10多年潜心研究这一算法的理论及进行12000余[14]-例实证研究的结果. 到目前为止尚未遇到反例. 由于不少学者根据NPC 理论认定这是绝对不可能的, 因此作者只好通过大量的实证研究来显示这一多项式算法存在的可能性. 况且, 作者进行这项研究的目的并不是为了解决计算复杂性理论中NP 是否等于P 的问题,而是为学术研究和工程应用提供一种在一般图中构造哈密顿圈的实用有效工具. 即便有人能找到反例, 说明SOA 算法只不过是像线性规划单纯形算法那样, 是一个实用的好算法, 应当说这也是一个很幸运的结果. 因为有了它, 不但可以在用相关定理(如范定理或者其它更新的定理)判定存在哈密顿圈的一般图中构造出至少一条具体的哈密顿圈, 也可以对超出这些定理范围之外的一般图进行是否是哈密顿图的判定, 这岂不也是一项有实用价值的成果. 如果这些研究结果还能对数学家们在解决哈密顿图判定的理论研究上有所启迪和帮助, 那么这项研究就更有意义了. 二、研究的基本内容, 拟解决的主要问题研究的基本内容: 1. 哈密顿图的判定;2. 哈密顿图的应用.解决的主要问题: 1. 判定一个图是否是哈密顿的必要条件.2. 判定一个图是否是哈密顿的充分条件.3. 哈密顿图问题的应用.三、研究步骤、方法及措施研究步骤: 1. 查阅相关资料, 做好笔记;2. 仔细阅读研究文献资料;3. 在老师指导下, 确定整个论文的思路, 列出论文提纲, 撰写开题报告;4. 翻译英文资料;5. 修改英文翻译, 撰写文献综述;6.撰写毕业论文;7. 上交论文初稿;8. 反复修改论文;9. 论文定稿.四、参考文献[1] 宁宣熙, 堵塞流理论及其应用[M]. 北京: 科学出版社, 2005.[2] Xuanxi Ning and Angelika Ning, The Blocking Flow Theory and its Application toHamiltonian Graph Problems[J]. Shaker Verlag. Aachen, 2006, 21(2): 286~318.[3] Ning Xuanxi. The Minimum Spanning Flow in a Network and its Self-organizationPrinciple[J]. The International Journal of Systems & Cybernetics, 2004, 33(2): 331~338.[4] Xuanxi Ning and Angelika Ning, The Minimum Spanning Flow Model of the HamiltonianPath Problem in a Digraph and its Polynomial Algorithm[J]. Information Processing and Management, 2006, 38(3): 356~361.[5] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003.[6] 同济大学应用数学系. 离散数学[M]. 上海: 同济大学出版社, 2003.[7] 王小东. 算法分析与设计[M]. 北京: 清华大学出版社, 1900.[8] 付寒冰, 周恒为. 数据结构中常用的三类算法[J]. 伊犁师范学院学报, 1997, 17(2):12~138.[9] 宁安琪, 宁宣熙. 金字塔图的哈密顿图性质研究[J]. 南京航空航天大学经济与管理学院学报, 2006, 21(3): 17~23.[10] 田媛, 刘铎. 金字塔图存在哈密顿回路的构造性证明[J]. 清华大学学报, 2007, 13(2): 38~52.。
组合数学的发展现状1985年9月，中国数学会组合数学与图论专业委员会成立，标记着中国组合数学学科的形成和创立，并于2001年正式成为中国组合数学与图论学会。
随着近年来组合数学理论体系的逐步完善和发展，越来越多的学者更加关注这一计算机与数学结合学科的发展。
中国数学会组合数学与图论专业委员会是中国数学会的分支机构，成立于1985年5月。
专业委员会的成立得到吴文俊先生的直接关心与支持。
首届专业委员会由25人组成，主任为徐利治。
专业委员会成立后，原有的全国组合数学研究会和全国图论研究会继续独立存在，各自组织活动。
直到2001年，两研究会正式合并成立中国组合数学与图论学会，同时完成了专业委员会的调整和换届。
专业委员会委员即学会常务理事；专业委员会主任，副主任即学会理事长，副理事长。
第一届专业委员会由26人组成，主任为范更华。
专业委员会于2004年在新疆乌鲁木齐组织召开了首届全国组合数学与图论大会，200多位代表参加了这次会议。
专业委员会于2004年在福州举办了为期三个月由福州大学离散数学研究中心承办的全国性研究生班，邀请海外留学人员利用学术休假回国开设完整的研究生课程，有50多位来自国内14所院校的研究生参加了这期研究生班。
专业委员会于2005年在福州举办了为期一个月由福州大学离散数学研究中心承办的全国性青年教师研讨班，旨在为组合数学与图论培养后继人才。
2005年3月在南京师范大学召开的理事长会议上草拟了学会的章程和关于举办学术会议的办法及工作程序，2005年6月在金华召开的第三届海峡两岸图论与组合数学会议上通过了这两个文件。
2006年8月学会在南开大学召开了第二届全国组合数学与图论大会，有400多位代表参加了此次会议。
由于第一届理事会四年任期已满，会议期间，学会根据章程进行了换届选举，南开大学陈永川当选为理事长。
在国外，组合数学早已成为十分重要的学科，甚至可以说是计算机科学的基础。
一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。
图论综述一、简介图论是数学的一个分支。
它以图为研究对象。
图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。
集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。
通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。
图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。
关于图论的文字记载最早出现在欧拉1736年的论著中，他所考虑的原始问题有很强的实际背景。
目前，图论已形成很多分支：如随机图论、网络图论、代数图论、拓扑图论、极值图论等。
图论的应用已经涵盖了人类学、计算机科学、化学、环境保护、非线性物理、心理学、社会学、交通管理、电信以及数学本身等。
二、基本内容2.1 图的基本概念本章首先介绍了图的一些基本性质和一些不同模型的图，包括偶图，完全图和补图，引入了定点度的来描述图的性质。
其次介绍了子图的相关概念，介绍了图的一些基本运算规则，对图的路和连通性进行了阐释。
紧接着讲解了最短路算法，定义设G为边赋权图。
u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。
图的代数表示，包括图的邻接矩阵和图的关联矩阵。
最后对极图理论进行了简介，主要介绍了极值图论中的一个经典结论——托兰定理。
2.2 树本章主要介绍了树的概念与性质，阐述了生成树与最小生成树的基本概念与一些常用结论与定理。
树是不含圈的无圈图，也是连通的无圈图。
树是图论中应用最为广泛的一类图。
在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。
图论的发展及其在生活中的应用数学与应用数学张佳丽指导教师刘秀丽摘要主要介绍了图论的起源与发展及其生活中的若干应用，如：渡河问题、旅游推销员问题、最小生成树问题、四色问题、安排问题、中国邮递员问题。
同时也涉及到了几种在图论中应用比较广泛的方法，如：最邻近法、求最小生成树的方法、求最优路线的方法等。
关键词图论生活问题应用Graph Theory Development and the Application in LifeMathematics and applied mathematics Zhang JialiTutor Liu XiuliAbstract This paper mainly introduces the origin and development of graph theory and its several applications in our life, such as: crossing river problem, traveling salesman problem, minimum spanning tree problem, four color problem，arrangement problem，Chinese postman problem．It also researches several methods that are more widely applied in graph theory, for example: the method of most neighboring, the method of solving the minimum spanning tree，the method of the best route，and so on．Key words graph theory life problem application引言图论是一门古老的学科，是数学中有广泛应用的一个分支，与其他的数学分支，如群论、矩阵论、概率论、拓扑学、数分析等有着密切的联系．图论中以图为研究对象，图形中我们用点表示对象，两点之间的连线表示对象之间的某种特定的关系．事实上，任何一个包含了二元关系的系统都可以用图论来模拟．而且,图论能把纷杂的信息变的有序、直观、清晰．由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点间连接与否尤为重要，而图形的位置、大小、形状及连接线的曲直长短则无关紧要．图论在自然科学、社会科学等各个领域都有广泛的应用．随着科学的发展，以及生产管理、军事、交通运输等方面提出了大量实际的需要，图论的理论及其应用研究得到飞速发展。
图论及其应⽤-哈密尔顿图（alpha）图论及其应⽤-哈密尔顿图(alpha)⼩结：2010-04。
todo 没有粘贴公式。
1重要的概念是闭包。
注意 ppt定义42重点汇总与闭包定理3其他的2个定理对⽐：（第⼀阶级：是不是两个反⾯）⼀个是存在不相邻的点u , v, 围绕 du + dv >=n; G 是H图，那么G+uv也是H图（66：增边）满⾜du + dv >=n 都有u,v相邻，那么G是闭包、本次课主要内容(⼀)、哈密尔顿图的概念(⼆)、性质与判定哈密尔顿图1、背景(⼀)、哈密尔顿图的概念1857年，哈密尔顿发明了⼀个游戏(Icosian Game).它是由⼀个⽊制的正⼗⼆⾯体构成，在它的每个棱⾓处标有当时很有名的城市。
游戏⽬的是“环球旅⾏”。
为了容易记住被旅游过的城市，在每个棱⾓上放上⼀个钉⼦，再⽤⼀根线绕在那些旅游过的城市上(钉⼦),由此可以获得旅程的直观表⽰。
哈密尔顿(1805---1865),爱尔兰数学家。
个⼈⽣活很不幸，但兴趣⼴泛：诗歌、光学、天⽂学和数学⽆所不能。
他的主要贡献是在代数领域，发现了四元数(第⼀个⾮交换代数)，他认为数学是最美丽的花朵。
哈密尔顿把该游戏以25英镑的价格买给了J.Jacques and Sons公司 (该公司如今以制造国际象棋设备⽽著名) ，1859年获得专利权。
但商业运作失败了。
该游戏促使⼈们思考点线连接的图的结构特征。
这就是图论历史上著名的哈密尔顿问题。
2、哈密尔顿图与哈密尔顿路定义1 如果经过图G的每个顶点恰好⼀次后能够回到出发点，称这样的图为哈密尔顿图，简称H图。
所经过的闭途径是G的⼀个⽣成圈，称为G的哈密尔顿圈。
例1、正⼗⼆⾯体是H图。
例2 下图G是⾮H图。
证明：因为在G中，边uv是割边，所以它不在G的任意圈上，于是u与v不能在G的同⼀个圈上。
故G不存在包括所有顶点的圈，即G是⾮H图。
定义2 如果存在经过G的每个顶点恰好⼀次的路，称该路为G的哈密尔顿路，简称H路。
第41卷 第1期吉林大学学报(信息科学版)Vol.41 No.12023年1月Journal of Jilin University (Information Science Edition)Jan.2023文章编号:1671⁃5896(2023)01⁃0112⁃06无桥图最短偶子图覆盖的上界收稿日期:2022⁃03⁃15基金项目:陕西省教育厅自然科学专项基金资助项目(16JK1243);陕西省自然科学基金资助项目(2020JM⁃629)作者简介:王晓(1980 ),男,河南南阳人,商洛学院副教授,博士,主要从事图论及其应用研究,(Tel)86⁃158****5250(E⁃mail)wangxiaomath@㊂王 晓,唐少茹(商洛学院数学与计算机应用学院,陕西商洛726000)摘要:偶子图覆盖问题是图论研究领域的的重要内容之一,为研究最小偶子图覆盖猜想,利用整数流与偶子图覆盖的联系,借助于整数4⁃流在图的某个圈中扩充的结论,给出并证明了无桥图的最小偶子图覆盖的一个新的上界,改进了范更华给出的结论㊂关键词:整数流;子图覆盖;最短偶子图覆盖中图分类号:TP301;O157.5文献标志码:AUpper Boundary of Shortest Cycle Covers of Bridgeless GraphsWANG Xiao,TANG Shaoru(School of Mathematics and Computer Application,Shangluo University,Shangluo 726000,China)Abstract :Even subgraph covers is an important subject in graph theory.Inorder to study the shortest cycle covers conjecture,using the connection between integer flows and even subgraph covers,a new upper boundary of shortest cycle covers of bridgeless graphs is obtained by means of the conclusion of expanding an integer 4⁃flow in a circuit of a graph.The result improves Fan’s conclusion.Key words :integer flow;subgraph covers;shortest cycle covers0 引 言四色问题是图论乃至数学史上最著名的问题之一,1977年Appel 等[1⁃2]借助计算机证明了四色问题㊂但仍有学者在继续研究四色问题,希望能找到一个纯数学推理的证明㊂Tutte 为了能在更大的框架内研究四色问题,给出了整数流的概念,并先后提出5⁃流猜想[3]㊁4⁃流猜想[4]和3⁃流猜想[5],构成了整数流理论研究的核心问题㊂四色问题等价于平面图的整数4⁃流问题㊂子图覆盖问题也与四色问题密切相关,四色问题还等价于平面图的偶子图覆盖问题:2⁃边连通的平面图是否存在3个偶子图使该平面图的每条边都恰好包含在其中的两个偶子图中㊂整数流和子图覆盖是图论领域的两个重要研究方向㊂最小偶子图覆盖猜想和双圈覆盖猜想(也称为偶子图2⁃覆盖猜想)是子图覆盖研究领域中的两个重要猜想㊂笔者主要研究无桥图的最小偶子图覆盖的上界问题,利用文献[6]中整数4⁃流的一个定理,改进了范更华[7]在2017年关于最小偶子图覆盖一个结论,得到了无桥图最小偶子图覆盖的一个更好的上界㊂1 基本概念及研究背景图G 是一个二元有序对(V (G ),E (G )),其中V (G )和E (G )分别为图的顶点集和边集㊂笔者考虑的图可能含有自环和平行边,需要用到但未给出定义的术语和记号可参阅文献[5,8]㊂对连通图G ,若存在边e ∈E (G )使G -e 有两个连通分支,则称e 为G 的桥(也称为割边)㊂若图H 满足V (H )⊆V (G )且E (H )⊆E (G ),则称H 为G 的子图㊂满足V (H )=V (G )的子图H 称为G 的生成子图㊂对顶点v ∈V (G ),称与v 关联边的数目(若是环,则计算两次)为顶点v 的度数㊂图G 中所有顶点中度数最小的顶点的度数称为G 的最小度数,用δ(G )表示㊂每个顶点的度数都为k 的图称为k⁃正则图,每个顶点的度数都为偶数的图称为偶图,连通的2⁃正则图称为圈㊂设τ为图G 的一个定向,Z 是整数加法群,f 为E (G )到Z 的映射,对顶点v ∈V (G ),定义∂τf (v )=∑e ∈N +(v )f (e )-∑e ∈N -(v )f (e ),其中N +(v )和N -(v )分别为图G 中在定向τ下背离和指向顶点v 的边的集合㊂若对任意的v ∈V (G )都有∂τf (v )=0,则称(τ,f )为图G 的一个整数流,且supp (f )={e ∈E (G ):f (e )≠0}为f 的支撑集㊂若supp(f )=E (G )且存在正整数k ,使对任意e ∈E (G )都有f (e )<k ,则称(τ,f )为图G 的无零整数k⁃流㊂若将整数加法群Z 改为整数模k 的剩余类加法群Z k ,自然地得到Z k ⁃流和无零Z k ⁃流㊂设F 1,F 2, ,F k 为图G 的子图,若有E (G )=E (F 1)∪E (F 2)∪ ∪E (F k ),则称子图簇X ={F 1,F 2,,F k }是图G 的一个子图覆盖㊂特别地,若X 中每个图都是偶图,则称X 是G 的偶子图覆盖;若X 中每个图都是圈,则称X 是G 的圈覆盖㊂因为每个偶图都是由边不交的圈构成,所以一个图有圈覆盖当且仅当它有偶子图覆盖㊂若子图簇X 是图G 的子图覆盖且X 中子图个数不超过k ,则称X 是图G 的k⁃子图覆盖㊂若X 是图G 的k⁃子图覆盖且G 中的每条边恰好包含在X 的两个子图中,则称X 为G 的k⁃子图双覆盖㊂图的偶子图覆盖与整数流密切相关,Matthews [9]有如下结论㊂定理1[9] 设k 是正整数,则图G 有无零整数2k ⁃流当且仅当G 有k⁃偶子图覆盖㊂1973年Szekeres [10]提出下面的猜想,称为偶子图双覆盖猜想(Cycle Double Cover Conjecture),它是子图覆盖的研究领域中最著名的猜想之一㊂猜想1[10] 无桥图有偶子图双覆盖㊂设X ={F 1,F 2, ,F k }是无桥图G 的偶子图覆盖,令C (X )=∑ki =1E (F i ),则G 的偶子图覆盖中总边数最少的偶子图覆盖的总边的数目称为G 的最小偶子图覆盖,记为S C (G ),即有S C (G )=min{C (X ):X 是G 的偶子图覆盖}㊂ 一个图若存在偶子图覆盖则它必然是无桥的㊂寻找无桥图的最小偶子图覆盖S C (G )的上界是偶子图覆盖研究领域的重要课题,Alon 等[11]在1985年提出了下面的最小偶子图覆盖猜想(Shortest Cycle Cover Conjecture)㊂猜想2[11] 设G 是无桥图,则有S C (G )≤1.4E (G )㊂同时,Alon 等[11]和Bermond 等[12]各自独立证明了无桥图的最小偶子图覆盖满足S C (G )≤53E (G ),截至目前此结果在无桥图上仍是最好的㊂1992年,Jamshy 等[13]证明了最小偶子图覆盖猜想(猜想2)暗含偶子图双覆盖猜想(猜想1)㊂设G 是无桥图,Jamshy 等[14]证明了若5⁃流猜想成立则S C (G )≤1.6E (G );Fan [15]证明了若3⁃流猜想成立,则S C (G )≤4427E (G );Fan 等[16]证明了若Fulkerson 猜想成立,则S C (G )≤2215E (G )㊂Kaiser 等[17]在2010年证明了对于最小度数至少为3的无桥图G 有S C (G )≤4427E (G )(≈1.6296E (G ))㊂ 2017年,Fan [7]又改进了他们的结果,得到如下结论㊂定理2[7] 设G 是无桥图且最小度数至少为3,则S C (G )<278171E (G )(≈1.6257E (G )),311第1期王晓,等:无桥图最短偶子图覆盖的上界并且若G 没有自环,则S C (G )≤218135E (G )(≈1.6148E (G ))㊂ 笔者改进了定理2的结果,得到了无桥图G 的最小偶子图覆盖的一个新上界:S C (G )≤394243E (G )+151243V 2(G )(≈1.6214E (G )+0.6214V 2(G )),其中V 2(G )表示图G 中度数为2的顶点集合㊂2 预备知识收缩图G 中的边e ,是指删掉边e 且粘合e 的两个端点(当e 不是自环时)㊂对G 的子图H ,用G /H表示由图G 收缩H 中所有边而得到的图㊂在文献[7]中,范更华提出了下面的猜想㊂猜想3[7] 设G 是无桥图且C 是G 中的一个圈㊂若G /C 有无零整数4⁃流,则图G 中存在一个整数4⁃流(τ,f )满足E (G )-E (C )⊆supp(f )和supp(f )∩E (C )>34E (C )㊂ Wang 等[6]证明了猜想3在E (C )≤27条件下是成立的㊂定理3[6] 设C 是无桥图G 中的一个圈㊂如果E (C )≤27且G /C 有无零整数4⁃流,则图G 上存在一个整数4⁃流(τ,f )满足E (G )-E (C )⊆supp(f )和supp(f )∩E (C )>34E (C )㊂ Tutte [18]证明了无桥图上的整数流和模流是等价的㊂定理4[18] 图G 有无零整数k⁃流,当且仅当G 有无零Z k ⁃流㊂设H 是图G 的一个子图,对G 上的整数流(或模流)(τ,f )和α∈Z (或α∈Z k ),令E f =α(H )={e ∈E (H ):f (e )=α}㊂ 笔者为了研究无桥图的最小偶子图覆盖的上界,基于定理3,有如下结论㊂引理1 设F 是无桥图G 的偶子图,并且(τ,f )是G 上的一个整数k⁃流,则存在G 上的整数k⁃流(τ,f′)满足supp(f′)-E (F )=supp(f )-E (F )和E f′=0(F )≤1kE (F )㊂特别地,当k =4且E (F )≤27,或E (F )不是k 的倍数时,存在图G 上的整数k⁃流(τ,f′)满足supp(f′)-E (F )=supp(f )-E (F )和E f′=0(F )<1kE (F )㊂证明:由定理4,可以在Z k ⁃流上证明引理1㊂同时,因为每个偶图都是由边不交的圈构成,所以只需证明F 是圈的情形即可㊂设(τ,f )是G 上的Z k ⁃流且F 是G 中的圈㊂显然,存在α∈Z k 使得E f =α(F )≤1kE (F )㊂不失一般性,设F 是定向τ下的有向圈,令f′=f -f α,其中f α=α,若e ∈E (F ),0,若e ∈E (G )\E (F {),于是(τ,f′)是G 上的Z k ⁃流,且满足supp(f )-E (F )=supp(f′)-E (F )和E f′=0(F )=E f =α(F )≤1kE (F )㊂ 当k =4且E (F )≤27时,由定理3,可知存在G 上的整数4⁃流(τ,f′)满足supp (f′)-E (F )=supp(f )-E (F )和E f′=0(F )<14E (F )㊂当E (F )不是k 的倍数时,则F 中含有边数不是k 的倍数的圈,记为C ,且存在G 上的整数k⁃流(τ,f′)满足supp (f′)-E (F )=supp (f )-E (F )和E f′=0(F )<1k E (F )-E (C )+1k E (C )=1kE (F )㊂411吉林大学学报(信息科学版)第41卷综上,引理1得证㊂同时,为证明笔者的主要结论,需文献[7]的如下3个引理㊂引理2[7] 设G 是无桥图且δ(G )≥3,则图G 有一个生成偶子图F ,使E (F )≥23E (G )且G /F 有无零整数4⁃流㊂引理3[7] 设F 是无桥图G 的偶子图,d l 是F 中有l 条边的分支数目㊂若G /F 有无零整数4⁃流,则有S C (G )≤3(V (G /F )-1)+E (G )+12E (F )-12∑i ≥0d 2i +1㊂ 引理4[7] 设F 是无桥图G 的偶子图㊂若(τ,f )是G 上的一个整数4⁃流且满足E f =0(G )⊆E (F ),则有S C (G )≤2E (G )-E (F )+2E f =0(G )㊂3 最小偶子图覆盖的上界下面笔者给出无桥图的最小偶子图覆盖的一个新的上界㊂定理5 设G 是无桥图,V 2(G )是G 中度数为2的顶点集合,则有S C (G )<394243E (G )+151243V 2(G )(≈1.6214E (G )+0.6214V 2(G ))㊂若图G 中没有自环且V 2(G )=Ø,则有S C (G )<334207E (G )(≈1.6135E (G ))㊂ 证明 将图G 的每个度数为2的顶点都添加一个自环,所得的图记为G′㊂于是有δ(G′)≥3且E (G′)=E (G )+V 2(G )㊂由引理2,可得图G′有一个生成偶子图F ,使E (F )≥23E (G′)且G′/F 有无零整数4⁃流㊂显然,此无零整数4⁃流可扩充到G′上的整数4⁃流(τ,f )且有E f =0(G′)⊆E (F )㊂设(τ,φ)是G′上的整数4⁃流,满足E φ=0(G′)⊆E (F )且使E φ=0(G′)尽量地小㊂令d l 表示F 中有l 条边的分支的数目,且F 1,F 2, ,F n 为F 中所有的连通分支㊂根据引理1,有E φ=0(G′)≤14∑E (F i )≥28E (F i )+14∑E (F i )<28E (F i )-14∑6k =0d 4k+1-24∑6k =0d 4k+2-34∑6k =0d 4k+3-∑5k =0d 4k+()4=14E (F )-14∑6k =0d 4k+1-24∑6k =0d 4k+2-34∑6k =0d 4k+3-∑5k =0d 4k+4㊂再结合引理4,即有S C (G′)≤2E (G′)-E (F )+2E φ=0(G′)≤2E (G′)-12E (F )-12∑6k =0d 4k +1-∑6k =0d 4k +2-32∑6k =0d 4k +3-2∑5k =0d 4k +4㊂(1)因为F 为图G′的生成偶子图,且F 的每个分支F i (1≤i ≤n )都对应于G′/F 中的一个顶点,所以V (G′/F )=n =∑E (F )i =1d i ≤∑27i =1d i +128E (F )-∑27i =1id ()i =128E (F )+∑27i =128-i28d i ㊂结合引理3,即有S C (G′)≤3(V (G′/F )-1)+E (G′)+12E (F )-12∑i ≥0d 2i +1≤E (G′)+1728E (F )+3∑27i =128-i 28d i -12∑i ≥0d 2i +1-3㊂(2)511第1期王晓,等:无桥图最短偶子图覆盖的上界利用不等式3∑27i =128-i 28d i ≤8128∑6k =0d 4k +1+7828∑6k =0d 4k +2+7528∑6k =0d 4k +3+7228∑5k =0d 4k +4,可得S C (G′)<E (G′)+1728E (F )+6728∑6k =0d 4k +1+7828∑6k =0d 4k +2+6128∑6k =0d 4k +3+7228∑5k =0d 4k +4㊂(3)式(1)的两边乘以6714,再加上式(3)可得8114S C (G′)<14814E (G′)-5028E (F )㊂根据E (F )≥23E (G′),即有S C (G′)<181×148E (G′)-503E (G′())=394243E (G′)㊂因此S C (G )=S C (G′)-V 2(G )<394243E (G′)-V 2(G )=394243(E (G )-V 2(G ))-V 2(G )=394243E (G )+151243V 2(G )㊂ 若图G 中没有自环且V 2(G )=Ø,则d 1=0㊂于是,式(1)和式(2)分别为S C (G )≤2E (G )-12E (F )-12∑6k =1d 4k +1-∑6k =0d 4k +2-32∑6k =0d 4k +3-2∑5k =0d 4k +4,(4)S C (G )≤E (G )+1728E (F )+3∑27i =228-i 28d i -12∑i ≥1d 2i +1-3㊂(5)将不等式3∑27i =328-i 28d i ≤6928∑6k =1d 4k +1+7828∑6k =0d 4k +2+7528∑6k =0d 4k +3+7228∑5k =0d 4k +4代入式(5),可得S C (G )<E (G )+1728E (F )+5528∑6k =1d 4k +1+7828∑6k =0d 4k +2+6128∑6k =0d 4k +3+7228∑5k =0d 4k +4㊂(6)式(4)的两边乘以5514,再加式(6)可得6914S C (G )<12414E (G )-3828E (F )㊂根据引理2,有E (F )≥23E (G )㊂所以S C (G )<169×(124E (G )-383E (G ))=334207E (G )㊂ 综上,定理5得证㊂4 结 语最短偶子图覆盖问题不仅是一个离散优化问题,其与图论研究领域中的一些主流问题,如:Tutte 整数流猜想㊁双圈覆盖猜想㊁Fulkerson 猜想㊁Snark 图和图子式等,都密切相关㊂想要完全证明Alon 等[11]在1985年提出的最小偶子图覆盖猜想(猜想2)是比较困难的,确定无桥图最小偶子图覆盖的上界是研究该问题的一个主要方向㊂笔者通过研究,得到了无桥图最小偶子图覆盖的一个新的上界,改进了范更华[7]在2017年给出的结论㊂611吉林大学学报(信息科学版)第41卷参考文献:[1]APPEL K,HAKEN W.Every Planar Map is Four Colorable,Ⅰ:Discharging [J].Illinois J Math,1977,21:429⁃490.[2]APPEL K,HAKEN W,KOCH J.Every Planar Map is Four Colorable,Ⅱ:Discharging [J].Illinois J Math,1977,21:491⁃567.[3]TUTTE W.A Contribution to the Theory of Chromatic Polynomials [J].Canadian Journal of Mathematics,1954,6:80⁃91.[4]TUTTE W.On the Algebraic Theory of Graph Colouring [J].Journal of Combinatorial Theory,1966(1):15⁃50.[5]BONDY J,MURTY U.Graph Theory [M].New York:Springer,2008.[6]WANG X,LU Y,ZHANG S.Note on Integer 4⁃Flows in Graphs [J /OL].Acta Mathematica Sinica,English Series:1⁃12.[2022⁃03⁃12].https:∥ /kcms /detail /11.2039.O1.20220106.1527.004.html.[7]FAN G H.Integer 4⁃Flows and Cycle Covers [J].Combinatorica,2017,37:1097⁃1112.[8]范更华.整数流与子图覆盖[J].中国科学:数学,2017,47:457⁃466.FAN G H.Integer Flows and Subgraph Covers [J].Scientia Sinica:Mathematica,2017,47:457⁃466.[9]MATTHEWS K.On the Eulericity of a Graph [J].Journal of Graph Theory,1978,2:143⁃148.[10]SZEKERS G.Polyhedral Decompositions of Cubic Graphs [J].Bulletin of the Australian Mathematical Society,1973,8:367⁃387.[11]ALON N,TARSI M.Covering Multigraphs by Simple Circuits [J].SIAM Journal on Algebraic Discrete Methods,1985,6:345⁃350.[12]BERMOND J,JACKSON B,JAEGER F.Shortest Coverings of Graphs with Cycles [J].Journal of Combinatorial Theory,Series B,1983,35:297⁃308.[13]JAMSHY U,TARSI M.Short Cycle Coversand the Cycle Double Cover Conjecture [J].Journal of Combinatorial Theory,Series B,1992,56:197⁃204.[14]JAMSHY U,RASPAUD A,TARSI M.Short Circuit Covers for Regular Matroidswith a Nowhere Zero 5⁃Flow [J].Journal of Combinatorial Theory,Series B,1987,42:354⁃357.[15]FAN G H.Tutte’s 3⁃Flow Conjecture and Short Cycle Covers [J].Journal of Combinatorial Theory,Series B,1993,57:36⁃43.[16]FAN G H,RASPAUD A.Fulkerson’s Conjecture and Circuit Covers [J].Journal of Combinatorial Theory,Series B,1994,61:133⁃138.[17]KAISER T,KRAL D,LIDICKY B,et al.Short Cycle Covers of Graphs with Minimum Degree Three [J].SIAM Journal on Discrete Mathematics,2010,24:330⁃355.[18]TUTTE W.On the Imbedding of Linear Graphs in Surfaces [J].Proceedings of the London Mathematical Society,1949,51:474⁃483.(责任编辑:刘俏亮)711第1期王晓,等:无桥图最短偶子图覆盖的上界。
