关于特殊图上的两类控制数的研究

发布时间：2021-08-16 09:15

　　图论是以图作为研究对象,以探究事物以及事物之间关系为研究目的,且有着丰富的历史背景和实用价值的一门的数学学科。随着信息技术的不断突破以及各学科之间的交叉融合,图论的发展进入到了一个新时代。它不仅仅在蛋白质结构的研究、交通网络图的绘制、电路图的设计、计算机编程等方面有着广泛的应用,在逻辑学、语言学、通讯网络等领域的应用也尤为突出,应用范围不断的拓广。控制问题一直是图论领域的研究热点。已有结论表明图的控制数问题是一类NP—完备问题,因此探究出图的控制数的精确值或者控制数较好的上下界具有重大的理论意义。本文以图的强罗马控制数和意大利控制数作为研究对象,针对一些特殊图上的强罗马控制数和意大利控制数的界及性质进行深入的研究和讨论,主要工作包括:首先,概述了图论的起源和发展历程,阐述了图的罗马控制、强罗马控制和意大利控制问题的研究背景、研究现状以及研究意义,并给出了一些有关符号和定义。其次,利用归纳法对完全图的刺图、扇图的中间图、完全二部图等特殊图上的强罗马控制数进行数学推导,得出了这些特殊图的强罗马控制数的上界,验证了“对所有n ≥3的连通图G有γStR（G）≤6n/7成立”的猜想在这部分特殊图... 

【文章来源】：大连海事大学辽宁省 211工程院校

【文章页数】：45 页

【学位级别】：硕士

【部分图文】：

图２．?３扇图的中间图??Ｆｉｇ．?２．３?Ｍｉｄｄｌｅ?ｇｒａｐｈ?ｏｆ?ｆａｎ?ｇｒａｐｈ??

?关于特殊图上的两类控制数的研究???Ｖ〇?ｖｏ??（？）?Ｆ４?（Ａ）?Ｍ｛Ｆ４）??图２．?３扇图的中间图??Ｆｉｇ．?２．３?Ｍｉｄｄｌｅ?ｇｒａｐｈ?ｏｆ?ｆａｎ?ｇｒａｐｈ??格子图ｔ３％两个路径图分别为ｇ?＝?ｐ？，和／／?＝?ｐ？，它们的笛卡尔乘积图称为〃＾？的??格子图，记做乂．？。??并图ｉ３６］：若图ｇ，和图ｇ２不相交，且组合的图形的顶点集合与边集合分别满足??以ＧｊＵＫｑ）与五（ＧｊＵＭＧ），则组合后的图形称为图Ｇ，和图Ｇ２的并图。由Ｐ个图??Ｇ共用一个顶点的并图记作图ｉ＼ｃ［３６ｌ。??双星：仅有两个非叶子结点的树。两个支撑顶点上分别连接；？，ｇ个叶子顶点的??双星图记作??符号坏和分别对应表示星图４的剖分图和双星图的剖分图，也称为剖??分星和剖分双星。当？为大于等于２的正整数时，图也被称为健康的蜘蛛图，当星??图内的剖分边的数目至多为时，则称此时的剖分星图；为病态的蜘蛛图或者??受伤的蜘蛛图。在图中，若＜ｖ）?＝?（则称顶点ｖ为蜘蛛图的头顶点，所有满足条件??出麵…，ｖ）二２的顶点《被称为蚨丨蛛图的脚顶点，如图２．４所示。??图２．?４蜘蛛图??Ｆｉｇ．?２．４?Ｓｐｉｄｅｒ?ｇｒａｐｈ??－１２－??


本文编号：3345404