κ割宽临界树的一些构造方法（κ≥3）.pdf.pdf

维普资讯
第卷第期天中学刊、, .
年月.
宽临界树的一些构造方法≥
张振坤,余春华
黄淮学院,河南驻马店
摘要:起源于超大规模集成电路设计和网络通讯的图的割宽问题,就是把一个含有个顶点的图
的全部顶点分剐安装在一条直线的不同的整数点上,使得跨越各项点的边数的最大值即稠密度达到最小.
文章得到了七一割宽临界树的一些构造方法七≥
关键词:割宽;树;临界树
中图分类号:. 文献标识码: 文章编号:...
定义图的割宽
引言
,/,
作为一类重要的组合最优化问题——图的安装问其中的最小值取遍所有的标号
题的一个组成部分,图的割宽问题就是把定义设厂是图的一个标号,如果
一个含有”个顶点的图的全部顶点分别安装在一条
,,
直线不同的整数点上,使得跨越各顶点的边数的最大则称厂是图的最优割宽标号.
, 如果我们令
但在超大规模集成电路的设计】、信息交换
≤.,≤”,那么图的标号. 厂就可以看作把图的
和网络通讯】、并行计算机的互联网络设计、编码理顶点,,⋯,
论等领域均有重要的应用,而且它还与其他的图论参
,记为具有前. ,个标号的顶点集, 即
数一一带宽、路宽、树宽
, , ,⋯,,,边集:≤为嵌
以及图的搜索数等有着密切的联系【. 入/在【,】,图在标号/下的割宽
因此,它不但具有重要的实际应用背景,而且还具有,就等于所有割,,,⋯,”一中边
重要的理论意义. 数最大的割的边数,即
定义设,是一个简单连通图, , .

其中。, ,⋯,和分别
人们对图的割宽问题已经进行了很深入的研究.
. ÷,,⋯,”称
对一般图来讲, 图的割宽问题是一困难的
为图的一个顶点标号,其中/称
.【,即使把图限制为最大度为的图包
≤≤”,则
含平面图,此问题也是困难的【】.因此,它不可
., ,⋯, 就是的顶点在. 厂下的顺序.

标号厂表示把图的所有顶点嵌入到一条具有”
宽并且顶点的度不超过常数的图,..给
个顶点的路上. 出了计算其割宽的多项式时间算法【;另外,如果图
定义任意给定图的一个标号厂
是一棵树连通的简单无圈图,此问题在多项式时
,:/“≤/
间内是可解的【,文献已给出
称为图关于标号厂的割宽. 了很多详见文献【】.割宽和其他图论参数的联
收稿日期:..
基金项目:河南省自然科学基金项目
作者简介:张振坤,男,河南汝南人,黄淮学院数学科学系讲师,博士
维普资讯
张振坤,余春华:一割宽临界树的一些构造方法七≥· ·
系】,割宽至多为的临界图以及割宽为的临界· ·
树等都已得到了刻画】.在此基础上,本文得到了我们首先证明≤, 和乃均为一
一割宽临界树的一些构造方法七≥. 一割宽树,所以它们分别存在一个割宽为—的最优
除了一困难性以外,图的割宽还具有下列基本标号, 和. 对一,的三个分支
性质. , , —的顶点集一。,,一。,
引理