论文摘要
本文主要研究3×n和4×n棋盘的染色计数公式以及部分网格图的具有最大叶子独立数的支撑树构造.第一章我们介绍了染色计数、网格图支撑树、连通点覆盖与不可分独立集相关的研究现状和背景,以及本文需要用到的一些基本概念和引理.第二章讲述的是用k种颜色对3×n和4×n棋盘进行格子染色使得相邻格子异色的染色计数问题.我们利用加法、乘法原理,消元思想和特征值法,解方程得到了两个染色计数公式.第三章的研究对象是平面上的网格图,即P_m×P_n(m=2,3,4,5).我们对网格图所有支撑树的叶子独立集可能的情况做了分析和研究,得出了其叶子独立数的上界并构造出了满足要求的支撑树.根据图的不可分独立集性质,这也等价地给出了这类图的最大不可分独立集.考虑到最大不可分独立集是最小连通点覆盖集的一个对偶,我们也就得到此类网格图的最小连通点覆盖数.
论文目录
文章来源
类型: 硕士论文
作者: 徐倩倩
导师: 任韩
关键词: 棋盘,染色,网格图,叶子,独立集
来源: 华东师范大学
年度: 2019
分类: 基础科学
专业: 数学
单位: 华东师范大学
分类号: O157.5
总页数: 42
文件大小: 1468K
下载量: 25
相关论文文献
- [1].从独立集权走向综合分权:中国政府监管体系建设转向的过程与成因[J]. 中国行政管理 2020(10)
- [2].基于最大权重独立集的行人检测研究[J]. 宁波工程学院学报 2013(03)
- [3].两类树的独立集多项式的单峰性[J]. 高等数学研究 2010(04)
- [4].块图中的团横贯集和团独立集[J]. 通化师范学院学报 2010(04)
- [5].基于独立集划分的图着色算法[J]. 哈尔滨理工大学学报 2010(05)
- [6].独立集对策的核心稳定性[J]. 自然科学进展 2008(04)
- [7].一种改进的分布式最大权独立集算法[J]. 电子与信息学报 2012(03)
- [8].一类三角系统的匹配数与点独立集数[J]. 西南师范大学学报(自然科学版) 2009(01)
- [9].基于历史信息的局部最大权独立集感知无线电频谱分配算法[J]. 广西师范大学学报(自然科学版) 2012(04)
- [10].加权分治与皇冠技术求解最大加权独立集[J]. 计算机工程与应用 2017(09)
- [11].五角链关于独立集数的极端情形[J]. 集美大学学报(自然科学版)(网络预览本) 2010(04)
- [12].星形h多边形cactus的k-匹配与k-独立集[J]. 新疆师范大学学报(自然科学版) 2011(01)
- [13].五角链关于独立集数的极端情形[J]. 集美大学学报(自然科学版) 2010(04)
- [14].关于独立集可去的分数(k,m)-消去图的度和条件的注记[J]. 甘肃联合大学学报(自然科学版) 2013(05)
- [15].独立集可去的分数(k,m)-消去图的最小度条件[J]. 曲靖师范学院学报 2012(03)
- [16].三角系统T_n的匹配数与点独立集数[J]. 西南师范大学学报(自然科学版) 2010(01)
- [17].处理条件效果的互斥延迟算法的研究[J]. 东北师大学报(自然科学版) 2008(01)
- [18].图族路粘圈的m-指标的最大值[J]. 青海师范大学民族师范学院学报 2011(02)
- [19].随机图中k-独立集的相变性质[J]. 计算机研究与发展 2017(12)
- [20].k-阶圈链Q(C_(s_1),P_2,C_(s_2),…,P_2,C_(s_k))Hosoya指标最大值[J]. 大连理工大学学报 2015(06)
- [21].关于独立数问题的一些结果[J]. 四川兵工学报 2010(01)
- [22].分数ID-消去图的邻域并条件[J]. 昆明学院学报 2012(06)
- [23].图的k-独立集与Grbner基求解[J]. 工程数学学报 2012(05)
- [24].基于抽象相关关系的粗糙集研究[J]. 南京大学学报(自然科学版) 2010(05)
- [25].H2H/M2M共存场景下基于图论的干扰协调机制[J]. 计算机科学 2019(05)
- [26].一类图的独立多项式的指标[J]. 山西师范大学学报(自然科学版) 2009(04)
- [27].关于有限集上L-fuzzifying拟阵独立集系的基数[J]. 西北大学学报(自然科学版) 2013(02)
- [28].森林的非正常均匀染色[J]. 山东大学学报(理学版) 2010(08)
- [29].蛛形图的全图和中心图的均匀染色[J]. 浙江师范大学学报(自然科学版) 2011(01)
- [30].拟阵在网络安全中的应用[J]. 小型微型计算机系统 2015(08)