两条路的强乘积的带宽 |
| |
引用本文: | 沈韻秋.两条路的强乘积的带宽[J].中国科学技术大学学报,1980(4). |
| |
作者姓名: | 沈韻秋 |
| |
摘 要: | 图的带寬问題也称最优編号問題,它是与n阶矩陣系統求解所需最少时間密切相关的。决定一般图的带寬的算法即使对树来說都是NP一完全問題,因此寻求特殊图的带寬变成重要的問題了。除了很簡单的情况外,已获得带寬的特殊图类为数甚少。本文首先推广了Chvátalová1975年在1]文中的引理,即把两条路的乘积的位移不变子集具有最小边界性質拓广到强乘积,引入了正則位移不变子集概念,繼而获得了两条路的强乘积的带寬定理。記G为n个頂点的至少有一条边的图,頂点集V(G),边集E(G)。f为1—1映射:
|
本文献已被 CNKI 等数据库收录! |
|