论文部分内容阅读
图的厚度t(G),简单来说就是将图G分解成若干个平面子图的并的最少平面子图的数目.一般而言,确定图的厚度是一个NP-难问题,因此确定给定图的厚度的值是一项非常困难的工作.并且相对于其他图的拓扑参数,图的厚度的结果较少.对于完全二部图 m,nK的厚度, Beineke, Harary和Moon于1964年给出了如下计算公式(此处公式省略) 仅当m和n同时为奇数且存在整数 k使得n=[2k(m-2/(m-2k))不成立. 依据上述公式,完全二部图的厚度并未全部确定.著名图论学者 J.L. Gross和F. Harary在1980年《拓扑图论的一些问题》的综述论文中提出如下问题:对任意整数m, n,确定完全二部图 m,nK的厚度.本文试图对该问题进行研究,另外我们也对完全三部图的厚度进行了讨论. 第一章主要介绍图的厚度的起源,国内外的研究现状以及本文所需的一些基础知识,同时还简要的介绍了本文的基本结构. 第二章介绍了关于完全二部图厚度的Beineke-Harary-Moon定理的证明. 第三章给出了完全二部图Kn,n+4和Kn,n+8的分解,并确定了其厚度. 第四章对完全三部图的厚度进行了研究,确定了部分完全三部图的厚度.