[01551601]网络完全化问题及应用研究

本项目起源于这种大型稀疏矩阵的存贮与消去技术,是目前组合最优化学科中一个非常具有生机和活力的研究课题。该理论中的系列组合最优化问题如填充、侧廓、扩充侧廓、树宽、路宽、带宽、割宽等,在超大规模集成电路（VLSI）设计、通讯网络、数据结构、编码理论、分子生物学等学科领域也被提出。因此,其理论内容在数值计算、数据结构、编码理论、分子生物学、通讯网络、超大规模集成电路（VLSI）的布线设计等学科领域有一定的理论应用价值。本项目用降维、网络变换、树分解、网络标号等技术,系统研究了图或网络的最小填充数、侧廓、扩充侧廓、割宽、消去割宽以及最小亏格数等理论参数,研究结论在理论方面是对图论学科理论的充实,在实际应用方面对超大规模集成电路（VLSI）的布线设计、并行计算机设计、电话和计算机信息通讯等领域的管理与决策具有指导作用。同时,在推广应用方面,通过将一个复杂的道路或管道系统抽象一个网络,如分别将道路或管道交叉位置、道路或管道自身抽象为网络的点和边而形成道路或管道网络等,则根据本项目的研究结论,管理人员可以调配最少的人员对相应网络进行检修和维护,从而节省出部分人力和物力;对网络通信、计算机网络宽带、计算机数据传输,交通运输网络的效能改进和技术提升等工作,相关决策人员可以在有限的预算要求内,使用最少的人力、物力、财力完成相应工作,从而避免人、财、物的浪费,既增强了工作效率,又满足了社会需求。