| 环面上格子图Cm×Cn的带宽 |
| |
| 引用本文： | 李乔,陶懋颀,沈韵秋.环面上格子图Cm×Cn的带宽[J].中国科学技术大学学报,1981(1). |
| |
| 作者姓名： | 李乔 陶懋颀 沈韵秋 |
| |
| 作者单位： | 中国科学技术大学数学系
(李乔，陶懋颀)，中国科学技术大学数学系(沈韵秋) |
| |
| 摘 要： | 求一个图(Graph)——或一个对称矩陣——的带宽(Band width)是一个很有实际意义的組合問題。已經証明,即使对于树形图(Tree)来說,确定它的带宽問題也属于NP—完全类。因此,求出一些特殊类型的图的带宽就更加引人注目。事实上,能够定出其带宽的图很少。除了一些很簡单的情形外,迄今已知的主要結果只有完全偶图K_(m:n)、n維方体Q_n、平面格子图P_m×P_n和柱面上的格子图C_m×P_n。Dewdney在1976年所作的关于图的带宽的一篇綜述报告中,提出了三个沒有解决的問题。其中一个是求环面上格子图C_m×C_n的带宽。本文解决了这个問題,我們得到下述結果: 定理1.当m≠n且min(m,n)≥3时,环面上格子图C_m×C_n的带宽为2min(m,n); 定理2.当n≥3时,环面上格子图C_n×C_n的带宽为2n—1.
|
| 本文献已被 CNKI 等数据库收录！ |
|
