字典序积图的厚度的研究

发布时间：2021-09-05 13:23

　　在图论中,图G和H的字典序积（或合成图）G ·H是一个图,使得:G·H的顶点集是笛卡儿积V（G）×V（H）G· H中任何两个顶点（u,v）和（x,y）相邻当且仅当u与x在G中是相邻的或u = x且v与y在H中是相邻的。图G的厚度t（G）是将G分解成不交的平面子图的并的最少平面子图数。确定任意图的厚度是NP困难的,因此很难获得一个图的精确的厚度值。在本文中,我们将研究两条不同路图的字典序积的厚度以及路图和完全图的字典序积的厚度。第一章主要介绍图的厚度的起源还有本文所需的一些基本知识。第二章主要通过引入平面图及研究平面性的一些已知的结果。第三章主要介绍两类特定的图:图运算将应用的路图和完全图。第四章主要介绍字典序积的基本结构,展示其他图乘积的一些特殊性。在第五章主要研究两条路图的字典序积的厚度以及路图和完全图的字典序积的厚度。 

【文章来源】：湖南大学湖南省 211工程院校 985工程院校 教育部直属院校

【文章页数】：48 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 引言
    1.2 图的基本概念
    1.3 本文的安排及主要工作
第2章 图的平面性
    2.1 引言
    2.2 平面图的欧拉公式
    2.3 可平面图的表征或可平面性的标准
第3章 路图与完全图
    3.1 路图
    3.2 完全图
第4章 字典序积的基本结构
    4.1 乘积的产类
    4.2 字典序积图(或合成图)
第5章 计算字典序积图的厚度
    5.1 引言与定理
    5.2 两路图的字典序积的厚度或合成图的厚度
    5.3 路图和完全图的字典序积的厚度或合成图的厚度
结论
参考文献
致谢



本文编号：3385427