张振坤，叶希琼，庞留勇

(1.黄淮学院 河南 驻马店 463000；2.郑州电子信息工程学校 河南 郑州 450007)

0 引言

本文所考虑的图均为简单有限的连通图，文中图论概念均来源于文献[1]。自20世纪80年代图的标号(又称图的嵌入)问题提出以来，因为图的割宽与微电子芯片电路布线中一个称为“拥塞度(congestion) ”的基本物理参数密切相关[2-4]，所以有学者对图的割宽问题展开深入研究。简明地，设G=(V(G),E(G))是一个具有n=|V(G)|个顶点的图,Pn=x1x2…xn是一个具有n个顶点的路，其中V(G)={vi:1≤i≤n}为G的顶点集，E(G) ={vivj:1≤i,j≤n}为G的边集，xj(1≤j≤n)是Pn的顶点，将G的每个顶点vi分别嵌入到路Pn的相应一个顶点xj上(简称G到Pn的一个嵌入)，使得Pn上每一对连续的顶点xj,xj+1之间重叠的边数达到最小，这个最小边数就称为图G的割宽，表示为c(G)。这里的图G可以看成是一个微电子芯片的电路布线示意图，vi表示芯片电路板上的节点，边vivj表示连接节点vi,vj的电线。当这个电路安装在Pn上时，Pn上所有连续的顶点xj,xj+1之间重叠的电线根数的最大值就称为这个嵌入的拥塞度(congestion)，这是一个度量电路性能的基本物理参数，是图论中割宽问题的主要物理背景。同时，图的割宽问题与超大规模集成电路、网络通信等实际问题也有关联[2,3,5,6]。理论上，图的割宽还与其他一些图论参数，如图的带宽、路宽、树宽等紧密相关[3, 7, 8]。

对一般图G来说，割宽的计算问题是NP-困难的[9], 即使G是最大度为3的平面图[10]。因此，自图的嵌入问题提出以来，确定在多项式时间内割宽可计算的图类及其结构特征一直是该问题的主要研究内容。然而，由于该问题的难度较大，所以取得的科研成果相对较少。……