某些平面近似三角剖分图的带宽问题  

Some Problem of Bandwidth About Plane Near triangulation

作　　者：廖章钜[1] 

机构地区：[1]北京联合大学应用文理学院

出　　处：《北京联合大学学报》1997年第1期40-45,共6页Journal of Beijing Union University

摘　　要：Ｒ．Ｈｏｃｈｂｅｒｇ等给出了一种技巧去求任意平面图带宽的一个下界，并使用这种技巧证明了具有边长ｌ的三角剖分三角形Ｔｌ有带宽ｌ＋１，在此基础上做了以下工作：１）外界面为正六边形，其边长为ｌ的平面近似三角剖分图（记为ｌ）的带宽为２ｌ＋１；２）Ｔｌ的符合某种条件的子图（记为Ｔ（ｓ）ｌ）的带宽界为ｍ＋１≤Ｂ（Ｔ（ｓ）ｌ）≤ｍ＋２（其中ｍ为子图的最大层宽）；３）外界面为正方形，其边长为ｌ的平面近似三角剖分图（记为□ｌ）的带宽为ｌ＋１；４）满足某种条件，外界面为五边形的平面近似三角剖分图（记为ｌ，ｌ１———其中ｌ为最大层宽，ｌ－ｌ１为底宽，ｌ１≤ｌ）的带宽为ｌ＋１。On the basis of the work of R. Hochberg etc., the following results are obtained. 1)The bandwidth of the plane near triangulation with the exterior cycle, which have six sides with side length l (labeled with l ) is exactly 2 l +1 2)The bandwidth of the subgraph of the T l (labeled with T (s) l ) is m+1≤B(T (s) l)≤m+2 , where m is max level width. 3)The bandwidth of the plane near triangulation with the exterior cycle, which have four sides with side length l (labeled with □ l ) is exactly l+1 . 4) The bandwidth of the plane near triangulation with the exterior cycle, which have five sides (labeled with l,l 1 ,where l is max level width and l-l 1 is floor width) is exactly l+1 . [

关 键 词：带宽 三角剖分图 平面图 图论 

分 类 号：O157.5[理学—数学]