直线簇上区间图的两类控制参数的算法

《直线簇上区间图的两类控制参数的算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、2005年上海大学硕士学位论文IIIKeywords：graphtheory,dominatingseteflgorithms，intervaigraphs、independentdomiuilliilgset,，I!011]flt{ct(!ddominatiligs(、t，flvnnHll(1progrannnhlg原创性声明本人声明，所呈交的论文是本人在导师的指导下进行的研究工作，除文了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果，参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意．

2、虢障慨日期：研年／月尹日本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分内容保密的论文在解密后应遵守此规定魏脚移一名：扁勾买日期：例年6月留El第一章引言§1．1图的控制参数问题的来源图论是现代数学的一个重要分支，它在数学学科方面(如群论、矩阵论、数值分析、概率论、拓扑学、点阵论和组合论等)有着广泛的应用，而且由于它所具有的用图表示的直观性，使得它在信息社会的一些学科领域，例如计算机、运筹学、系统工程、电子学以及物理学、生物学、社会科学和经济

3、问题等方面的模拟系统中都发挥了很大的作用．图论中有许多著名问题如最小树问题，最短路问题，网络流问题，图的控制问题，匹配问题，染色问题，旅行商问题，中国邮递员问题．由于它们具有很大的理论意义和极强的应用背景，因此受到了极大关注，许多专家学者都投入到其中的研究，从而使图论成为了现代应用数学中一个快速发展的重要分支。图的控制参数理论是图论中一个非常活跃的研究方向，其思想萌芽最早可以追溯到四百多年前在印度的一种棋盘游戏，在国际象棋的比赛中，出现了控制集的概念，棋赛的目的就是用某些棋子覆盖或者控制棋盘上的所有格子．1862年Dedaenisch考虑了控制整个

4、棋盘所需要的最少的皇后个数问题(皇后能越过任何几个空格，沿水平线，垂直线或者对角线移动．所谓控制整个棋盘是指每个格子或者已由某个皇后占领，或者可由某个皇后在一次移动后占领)，这种皇后的最小个数是5．这就是著名的五皇后问题[41L它可以看做是控制数的最早雏形．如果两个皇后中的一个皇后所在的格子能被另一个皇后经过一次移动到达，那么称这两个皇后是相互攻击的，否则就是互不攻击的．如果棋盘上的每个格子总能被某个皇后到达而且这些皇后之问又是互不攻击的，那么满足这种情况的皇后的最小个数是7．事实上，这种棋盘问题和图的控制集之间有着直接的联系．将图的顶点集与棋盘上

5、的似个格子一一对应，且两个顶点在图中是邻接的当且仅当两个对应格子中的一个格子可以由位于另一个格子中的皇后所控制，这样的图就称为皇后图，那么控制棋盘中全部格子的皇后的最小个数就是图的控制数，控制棋盘中全部格子的互不攻击的皇后的最小数目就是图的独立控制数，即独立控制集的最小基数．随后人们对此进行了初步的数学研究，最初只是集中研究”×n棋盘的各类控制数．这些渗透于日常生活中的数学理论大大地引起了人们对控制数概念的兴趣，1901年Ahrems的著作中对此做了详尽的阐述．现代的图的控制参数理论大家公认的是1958年由Berge和1962年由o，，e共同建立的

6、．1958年，Berge在其图论专著中首次提出了“控制数”这一概念，而到了2005年上海大学硕士学位论文21962年，Or，8在其图论著作中，正式定义并使用目前一直沿用的控制数方面的术语“dolniazlt&lgset”和“dominationnttmber”．1975年Cockayne和Hedetnieni概述了图的控制理论结果(在这篇综述报告中，他们首次开始使用符号n(G)表示图G的控制数，而且一直沿用至今)在1990年，《DiscreteMathmnatics》(VOL86)专门刊出了一期专辑，全面的介绍了控制参数理论方面的研究进展．在199

7、8年，Haynes等人编写了有关图的控制参数理论的两部专著ⅨFundamentalsofDominationinGraphs》，ⅨDomimationinGraphs：AdvancedTopics》，对1998年以前的各种控制参数的研究进行了综述。这两本经典专著的出版，为人们深入研究图的控制参数理论奠定了坚实的撼础，同时也巩固了图的控制集理论在图论中的地位，使得图的控制集理论得到了空前的发展．在2000年AMS分类目条中专列了一项05C69为Dominatingsets，independentsets，cliques这从一个侧面反映了它突飞猛进的发

8、展速度．在过去的的三十年里，尤其是近10年来，图的控制(domination)理论方面的研究E!成为图论中发展最快的领域之