毛虫树的扩充侧廓  

The Extended Profile of the Caterpillars

作　　者：张振坤[1] 封平华[2] 

机构地区：[1]黄淮学院,河南驻马店463000 [2]河南教育学院,河南郑州450000

出　　处：《天中学刊》2008年第5期1-5,共5页Journal of Tianzhong

基　　金：河南省科学发展计划基础与前沿技术研究项目(082300460190;082300410040)

摘　　要：起源于20世纪50年代的稀疏矩阵的存贮和消去技术的图的扩充侧廓问题就是在一个图G中寻求一个内含边数最小的边集F,使得超图G+F是单位区间图.G+F的边数|G+F|称为图G的扩充侧廓,表示为(?)(G);最小值|F|称为图G的单位区间完全数,表示为pic(G).文章得到了毛虫树的扩充侧廓的多项式时间算法和直径为4的特殊毛虫树的扩充侧廓具体表达式.The extended profile problem of a graph of the storage and elimination technique in 1950＇s is to find a set F with least edges in graph G, and make the graph G＋F is a proper interval graph. The edge number ｜G＋F｜ of G＋F is called the extended profile, denoted as ~↑P（G）, and the minimum value ｜F｜ is called the proper interval complete number, denoted as pic（G）. This paper provides a polynomial time algorithm to compute the extended profile of the caterpillars, and as an instance, the extended profile ~↑P（G） for the caterpillars with diameter four is given.

关 键 词：扩充侧廓 毛虫树 算法 

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