关于图的逆符号控制

《关于图的逆符号控制》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据关于图的逆符号控制Reversesigneddominationofgraph作者：裴良珍Author：坠i塑g圣塾皇望里皇i指导教师：吕新忠专业：系统理论学位：理学硕士授予单位：浙江师范大学Supervisor：圣i望兰坠Q翌g坠!Degree：丛asterofScienceInstitute：．——ZhejiangNormalUniversity．——May．,2014万方数据摘要图的控制数理论作为图论的一个重要研究领域已经得到国内外学者广泛研究，并在组合优化、计算机科学、通讯网络、社会学等领域中得到重要的应用。近年来，图的控制理论的定义和形式越来越多元化，同时由于图的控制问

2、题是NP．完全问题，因此研究图的控制数的上下界甚至精确估计以及彼此的相互关系是目前研究的主要方面。本文的研究对象是：图的逆符号控制，包括图的逆符号边控制、逆符号边全控制以及逆符号边全k控制。主要包括以下三个方面：第一，我们给出了一般图的逆符号边控制数的两个新的上界和正则连通图仅依赖于其点数的一个上界。第二，我们给出了一般图的逆符号边全控制数的两个新上界，并得出一个推论。第三，我们新定义了一类控制函数一图的逆符号边全k控制函数，同时给出了图的逆符号边全k控制数的两个上界。关键词：逆符号边控制；正则图：逆符号边全控制；逆符号边全七控制万方数据REVERSESIGNEDDONⅡ：c、法TION

3、OFGRAPHABSlRACTAsallimportantresearchfieldingraphtheory,dominationtheoryhasmanyandvariedapplicationsinrelatedsciencefields，suchascombinatorialoptimization,computerscience，communicationnetwork,sociologyandSOon．Inrecentyears，theformandthedefmitionofdominationtheoryismoleandmolediversified．Atthesame

4、time，becauseofdominationtheoryisNP-completeproblems，theupperandlowerboundsofdominationnumbersaswellastheirrelationshipisthemainaspectofrecentresearch．Thisthesismainlystudythreedominationnmnbers：reversesignededgedomination,reversesignededgetotaldominationandreversesignededgetotalkdomination．Itmain

5、lyincludesthefollowingthreeparts：(1)Wegivetwonewupperboundsofreversesignededgedominationnumbersofgeneralgraphsandaupperboundofregularconnectedgraphsonlydependsonitspoints．(2)Wegiveainferenceandtwonewupperboundsofreversesignededgetotaldominationnumbersofgeneralgraphs．(3)Wenewdefineaclassofdominati

6、on-reversesignededgetotalkdomination．Wealsogivetwoupperboundsofreversesignedcdgetotalkdominationnumbersofgeneralgraphs．KEYWORDS：ReverseSignedEdgeDomination；RegularGraph；ReverseSignedEdgeTotalDomination；ReverseSignedEdgeTotalkDomination2万方数据目录1绪论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一41

7、．1图的控制数理论背景介绍⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．41．2基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯-52．图的逆符号边控制数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72．1准备工作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯72．2图的逆符号边控制数的上界⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯83．图的逆符