一些多部图及笛卡尔积图的厚度

发布时间：2020-07-09 12:59

【摘要】：图G的厚度θ(G)是指图G可分解为平面生成子图的最小数.图的厚度是度量图的可平面性的重要指标之一,它在超大规模集成电路和网络设计中有着重要的应用.然而,由于图的厚度问题已经被证明是NP 难问题,所以目前已知厚度的图类很少.本论文主要研究了一些完全多部图,笛卡尔积图,联图和直积图的厚度以及一类完全三部图的4-围长厚度.论文第一章介绍了厚度的相关概念、研究背景以及本文研究的主要内容.第二章在完全二部图K_(n,n)的平面分解的基础上,构造了完全三部图K_(1,n,n)和K_(2,n,n)的平面分解,进而确定了完全三部图K_(1,n,n)和K_(2,n,n)的厚度.进一步地,基于完全三部图K_(2,n,n)的平面分解,构造了完全四部图K_(1,1,n,n)的平面分解,并得到了完全四部图K_(1,1,n,n)的厚度.图G和H的笛卡尔积图记为G H,其中顶点集V(G H)=V(G)×V(H),边集E(G H)={(g,h)(g~′,h~′)|gg~′∈E(G),h=h~′或hh~′∈E(H),g=g~′}.第三章研究了一些笛卡尔积图的厚度.对于大部分n值,得到了完全图K_n与圈C_m(m≥3)以及完全二部图K_(n,n)与圈C_m(m≥3)的笛卡尔积图的厚度,而且通过构造完全二部图K_(n,m)与路径P_k(k≥2)的笛卡尔积图的平面分解,确定了其厚度的上界和下界以及部分完全二部图K_(n,m)与路径P_2的笛卡尔积图的厚度的精确值,随后得到了完全二部图K_(n,n)与路径P_k(k≥2)的笛卡尔积图的厚度.图G和H的联图记为G+H,其中顶点集V(G+H)=V(G)∪V(H),边集E(G+H)={(v_i,u_j)|v_i∈E(G),u_j∈E(H)}∪E(G)∪E(H).第四章研究了圈与圈、路径与路径以及圈与路径的联图的厚度,进而研究了任意图与圈的联图的厚度.图G和H的直积图记为G×H,其中顶点集为V(G×H)=V(G)×V(H),边集E(G×H)={(g,h)(g~′,h~′)|gg~′∈E(G),hh~′∈E(H)}.第五章主要研究了完全图与路径的直积图的厚度.图G的g-围长厚度θ(g,G)是指图G分解为平面子图的最小数,其中,每个平面子图的围长至少是g.它是厚度的推广,3-围长厚度θ(3,G)就是图G的厚度θ(G).在第六章,我们得到了所有完全三部图K_(n,n,n)的4-围长厚度,并确定了完全图K_(10)的4-围长厚度.
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 郭美美;;从广义笛卡尔积解关系代数除法[J];现代计算机(专业版);2016年17期

2 斯钦;阿勇嘎;;图的笛卡尔积图的结构及其完美性(英文)[J];宝鸡文理学院学报(自然科学版);2011年04期

3 黄琼湘;广义笛卡尔积图的连通度[J];新疆大学学报(自然科学版);1991年02期

4 尤玲;叶永升;;圈与路笛卡尔积的边连通测地数[J];淮北师范大学学报(自然科学版);2018年01期

5 孙秀玲;;笛卡尔积在配件替互换关系中的研究与应用[J];科技创新导报;2010年13期

6 董新芳;田双亮;董新菊;;路的三类积图的无圈全染色[J];兰州文理学院学报(自然科学版);2017年05期

7 王倩;田双亮;;圈与偶图的笛卡尔积图的邻点可区别全染色[J];鲁东大学学报(自然科学版);2011年01期

8 张莉茜;黄元秋;;G_7×S_n的交叉数[J];湖南文理学院学报(自然科学版);2011年04期

9 吕胜祥;黄元秋;;几个六阶图与路的笛卡尔积的交叉数(英文)[J];湖南文理学院学报(自然科学版);2007年02期

10 马庆媛;田双亮;;若干笛卡尔积图的星全染色[J];云南民族大学学报(自然科学版);2011年03期

相关会议论文 前2条

1 蔡庆生;李凡长;徐金辉;;Fuzzy数学在知识量化形式化推理中的几点应用[A];复杂巨系统理论·方法·应用——中国系统工程学会第八届学术年会论文集[C];1994年

2 张振东;耿昕;杜朝晖;;模糊PID控制[A];1995年中国智能自动化学术会议暨智能自动化专业委员会成立大会论文集（上册）[C];1995年

相关博士学位论文 前8条

1 唐玲;关于一些特殊图类的交叉数研究[D];湖南师范大学;2007年

2 周志东;图的交叉数有关问题研究[D];湖南师范大学;2013年

3 袁梓瀚;关于循环图及一些特殊图与路、星、树和圈的笛卡尔积的交叉数研究[D];湖南师范大学;2009年

4 王晶;若干图类交叉数的研究[D];湖南师范大学;2009年

5 郭婷;图嵌入分布及相关性质[D];湖南师范大学;2013年

6 陈卫东;数据质量模型及关系代数运算下质量传递理论与方法研究[D];国防科学技术大学;2007年

7 张国珍;图的容错参数[D];山西大学;2014年

8 葛铁铮;图像搜索中的紧凑表达[D];中国科学技术大学;2014年

相关硕士学位论文 前10条

1 郭霞;一些多部图及笛卡尔积图的厚度[D];天津大学;2018年

2 赵晓晓;关于两类特殊图的交叉数的下界[D];湖南师范大学;2018年

3 李慧静;几类图的笛卡尔积的拓扑指标[D];天津大学;2017年

4 古媛媛;联图与笛卡尔积图类的交叉数研究[D];湖南师范大学;2017年

5 丁奇;n条路的笛卡尔积图的匹配排除和条件匹配排除[D];兰州大学;2014年

6 赵琳;关于图的交叉数[D];北京交通大学;2007年

7 吕胜祥;五阶图与星图的笛卡尔积的交叉数[D];湖南师范大学;2007年

8 张玉红;一些图的点邻点可区别全染色[D];兰州交通大学;2010年

9 刘永平;一些特殊图类的笛卡尔积和倍图的邻点可区别的全染色问题[D];兰州大学;2006年

10 戴庆华;关于图的交叉数研究[D];湖南师范大学;2009年

本文编号：2747492